CODEWITHSUNDEEP
haskell
softshipper
softshipper

Reputation: 34081

How to use the type and why compiler complains infinite type?

I have following type:

newtype Moi s a =
  Moi { runMoi :: s -> (a, s) }

the data constructor expects a function as the argument and it should return a tuple.

I tried following: 

*OwnState> :t Moi (+1)

the compiler complains:

<interactive>:1:6: error:
    * Occurs check: cannot construct the infinite type: s ~ (a, s)
      Expected type: s -> (a, s)
        Actual type: (a, s) -> (a, s)
    * In the first argument of `Moi', namely `(+ 1)'
      In the expression: Moi (+ 1)

First look at the type signature of (+1):

*OwnState> :t (+1)
(+1) :: Num a => a -> a

The type a has to be constraint to Num typeclass.

So when I write Moi (+1), what is going to happen, how the type is going to be substitute?

Let's analyze the error message as the next step:

Occurs check: cannot construct the infinite type: s ~ (a, s)

Tilde means ~ type equality and how the compiler comes to conclusion that s has the same type as (a, s)?

I suppose, the type substitution of example above works in this way:

n -> n "Type of (+1)
|    |
s -> (a, s)

then s becomes to (a, s) and the proof s ~ (a, s) is true. 

(a, s) -> (a, s)

But I can not see, why it is infinite type.

Upvotes: 3

Views: 76

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476659

But I can not see, why it is infinite type.

Because s occurs both at the left and right side of the type equality ~, and this in a recursive fashion. After one substitution, we have:

s ~ (a,s)

But note that s in (a,s) should also be substituted, so:

s ~ (a,s) ~ (a,(a,s)) ~ (a,(a,(a,s))) ~ ...

So in order to construct this type it would result in a type with infinitely nested 2-tuples. Haskell can not handle such types.

Moi (+1) simply does not match the specifications of this "state monad". You probably want to use:

Moi (\x -> (x,x+1))

or:

Moi (ap (,) (1 +))

Upvotes: 7

Related Questions