Does Higher order polymorphism require strict order of arguments?

Question

Reading LYAH, I stumbled upon this piece of code:

newtype Writer w a = Writer { runWriter :: (a, w) }

instance (Monoid w) => Monad (Writer w) where  
  return x = Writer (x, mempty)  
  (Writer (x,v)) >>= f = let (Writer (y, v')) = f x in Writer (y, v `mappend` v')  

While trying to understand what the heck is Writer w in the first line, I discovered this not being a full type, but a sort of type constructor with 1 argument, like Maybe for Maybe String

Looks great, but what if the initial type if Writer' is defined with swapped type arguments, like this:

newtype Writer' a w = Writer' { runWriter :: (a, w) } 

Is it possible to implement Monad instance now? Something like this, but what could actually be compiled:

instance (Monoid w) => Monad (\* -> Writer' * monoid) where

The idea of \* -> Writer' * monoid is the same as Writer w : A type constructor with one type argument missing -- this time first one.

Answer 1

This is not possible in Haskell, what you'd need is a type-level lambda function, which does not exist.

There are type synonyms which you can use to define reorderings of type variables:

type Writer'' a w = Writer' a w

but you can not give class instances for partially applied type synonyms (even with the TypeSynonymInstances extension).

I wrote my MSc thesis about the subject of how type-level lambdas can be added to GHC: https://xnyhps.nl/~thijs/share/paper.pdf to be used in type-class instances without sacrificing type inference.

Answer 2

What you are seeing here is a parochial design choice of Haskell. It makes perfect sense, conceptually speaking, to say that your Writer' type is a functor if you "leave out" its first parameter. And a programming language syntax could be invented to allow such declarations.

The Haskell community hasn't done so, because what they have is relatively simple and it works well enough. This isn't to say that alternative designs aren't possible, but to be adopted such a design would have to:

1. Be no more complex to use in practice than what we already have;
2. Offer functionality or advantage that would be worth the switch.

This generalizes to many other ways that the Haskell community uses types; often the choice to represent something as a type distinction is tied to some artifact of the language's design. Many monad transformers are good examples, like MaybeT:

newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }

instance Functor m => Functor (MaybeT m) where ...
instance Applicative m => Applicative (MaybeT m) where ...
instance Monad m => Monad (MaybeT m) where ...
instance MonadTrans MaybeT where ...

Since it's a newtype, this means that MaybeT IO String is isomorphic to IO (Maybe String); you can think of the two types as being two "perspectives" on the same set of values:

1. IO (Maybe String) is an IO action that produces values of type Maybe String;
2. MaybeT IO String is a MaybeT IO action that produces values of type String.

The difference between the perspectives is that they imply different implementations of the Monad operations. In Haskell then this is also tied to the following parochial technical facts:

• In one String is the last type parameter (the "values") and in the other Maybe String is;
• IO and MaybeT IO have different instances for the Monad class.

But maybe there is a language design where you could say that the type IO (Maybe a) can have a monad specific to it, and distinct from the monad for the more general IO a type. That language would incur some complexity to make that distinction consistently (e.g., rules to determine which Monad instance to by default for IO (Maybe String) and rules to allow the programmer to override the default choice). And I'd wager modestly that the end result would be no less complex than what we do have. TL;DR: Meh.