[Haskell-cafe] Why can't we make an instance declaration on a type synonym?

[Reid Barton]

On Mon, Jan 04, 2010 at 11:50:57AM -0500, Brandon Simmons wrote:
> On Sun, Jan 3, 2010 at 2:22 AM, Ivan Lazar Miljenovic
> <ivan.miljenovic at gmail.com> wrote:
> > jberryman <brandon.m.simmons at gmail.com> writes:
> >
> >> This may be a dumb question, but why can we not declare a Monad
> >> instance of a type synonym? This question came to me while working
> >> with the State monad recently and feeling that the requirement that we
> >> wrap our functions in the State constructor is a bit... kludgy.
> >>
> >
> > Because type defines an _alias_.  If you define "type Foo = Maybe Int",
> > then everywhere you have a "Foo" the compiler should be able to replace
> > it with "Maybe Int".
> >
> > As such, if you have a custom instance on your type synonym (say a
> > custom Show instance for Foo), then which instance will the compiler
> > use?
> 
> 
> Thanks. I guess what I'm really asking is if there is any way to
> redefine the monad instance for (->) such that we can have a State
> monad without the data constructor wrapper.

It would be a nightmare for type inference.  Consider:

return "foo" :: String -> (String, String)    -- \x -> ("foo", x)

which would be valid in a language where we can do what you suggest.
`return` has type `a -> m a`, so `a` must be `String`, and now we need
to unify `String -> m String` with `String -> String -> (String, String)`.
In Haskell, these just don't unify because there are no type-level lambdas.
Even if there were, how is the typechecker supposed to know that we want
the solution `m a = String -> (a, String)` and not `m a = a -> (a, a)`
or many other possibilites?

The purpose of the newtype State is to have something to unify `m` with:

return "foo" :: State String String

We can unify `String -> m String` with `String -> State String String`
by setting `m` to `State String`.

Regards,
Reid Barton