CODEWITHSUNDEEP
haskellmonads
user6023611
user6023611

Reputation:

Haskell - why does it has correct types?

I was disappointed about fact that it correct typing: 

renumberTree2' :: Tree a -> StateT Int Identity (Tree Int)
renumberTree2' t = get >>= (\v -> return (Empty))

After all, we have that:
(>>=) :: m a -> (a -> m b) -> m b. Due to the fact that StateT s m a we can't give to bind get :: StateT s m s. get is not of type m a as expected bind.
However, get s where s :: s->(a, s') is correct type which should be given to bind. Where am I wrong ?

Upvotes: 1

Views: 89

Answers (3)

Lee
Lee

Reputation: 144206

get has type m s where s is the state type. The MonadState instance for StateT has context:

Monad m => MonadState s (StateT s m)

so the monad type m is StateT s m. Therefore the type of get for StateT is:

(StateT s m) s

The function given to (>>=) must have type s -> StateT s m b for some result type b.

return (Empty)

has type StateT s m (Tree Int) as required since StateT s m is a monad .

Upvotes: 1

bheklilr
bheklilr

Reputation: 54078

You are mistaken in your reading of the types. You can treat higher kinded types (those with type parameters) much like you would functions with precedence. If you have a function

f :: a -> b -> c -> d -> e
f a b c d = undefined

Then calling it

let e = f a b c d

is equivalent to

let e = (((f a) b) c) d

Since f a :: b -> c -> d -> e, and so on for (f a) b, etc.

When you see the type StateT s m a, you can also read it as ((StateT s) m) a, the types are equivalent and GHC will happily accept that syntax. In this way it may be easier to see how Monad m => StateT s m a can be aligned with Monad m' => m' a':

m' ~ StateT s m
a' ~ a

This implies that the Monad m' in question is StateT s m. A simpler example that works in the exact same way is the Functor instance for Either a. It isn't Either that has a Functor instance, but Either a, since a Functor is a type with kind * -> *, meaning a type that takes only one type parameter.

Upvotes: 6

Thomas M. DuBuisson
Thomas M. DuBuisson

Reputation: 64750

After all, we have that: (>>=) :: m a -> (a -> m b) -> m b

> :type (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b

True.

get is not of type m a as expected [by] bind.

> import Control.Monad.State
> :type get
get :: MonadState s m => m s

No, get is of type m a (though it does carry a constraint).

Upvotes: 2

Related Questions