A Haskell tutorial ( https://www.fpcomplete.com/haskell/tutorial/monad-transformers/ ) says that, if we assume the following definition
newtype State s a = State (s -> (s, a))
then the following definition
newtype StateEither s e a = StateEither (State s (Either e a))
is a re-write of
newtype StateEither s e a = StateEither (s -> (s, Either e a))
What steps of substitution make this possible?
>Solution :
The two are not a rewrite of each other: a type checker will not deduce that the two are the same. The two are however very similar.
Indeed, the State type is defined as:
newtype State s a = State (s -> (s, a))
This means that for a State s a, it wraps an s -> (a, s) function into a State data constructor. If we thus remove the State data constructor, we can see this as a function with type s -> (a, s), so:
type State s a = s -> (s, a)
In that case the type State s (Either e a) thus has type:
s -> (s, Either e a)
and so:
newtype StateEither s e a = StateEither (State s (Either e a))
would be equivalent to:
newtype StateEither s e a = StateEither (s -> (s, Either e a))
Here a newtype is however used. This is useful to define a different instance for typeclasses, since an function is an instance of Monad as well, but we want to define a different instance for the Monad for a State.