[Haskell-cafe] ListT version leveraging Traversable

[Olaf Klinke]

Dear Juan, 

Traversables indeed are intimately connected with monad transformers:
Two monads are known to commute if one monad (say t) yields a functor on the Kleisli category of the other monad (say m). 
If you write down what this means for fmap, you get the following type signature:

(a -> m b) -> t a -> m (t b)

which is the type of mapM and traverse. So does every Traversable monad t yield a monad transformer? Not quite. A functor has to obey the law fmap f.fmap g = fmap (f.g) and this is not given simply by the existence of traverse, you need:

traverse f <=< traverse g = traverse (f <=< g).

As Li-yao Xia pointed out, it is fairly easy to find a counterexample to <*> = ap for TravListT. But you could of course define <*> = ap and the problem is gone. However, a lawful monad satisfies 

join . join = join . fmap join

and there is a counterexample for TravListT: 

type M a = TravListT [] a   -- [] is not commutative

x :: M Int
x = TravListT ([[1,2],[3,4]])

-- ((join.join) xxx) /= ((join.fmap join) xxx)
xxx :: M (M (M Int))
xxx = let xx = [[x, x],[x]] in TravListT [[TravListT xx,TravListT (reverse xx)]]

I have not attempted to make this counterexample minimal, so please forgive the long term. 
Your claim (3) that [] is the monad of non-determinism is at least not entirely true. Lists modulo ordering and multiplicity are a model of non-determinism. In other words, if Data.Set was a monad then this was your model of non-determinism. Indeed, we have 

((sort.runTravListT.join.join) xxx) == ((sort.runTravListT.join.fmap join) xxx)

so the counterexample is only a counterexample because the ordering matters for equality. If you're modelling non-determinism, you may safely use the deprecated ListT knowing that the monad laws are violated only due to ordering and multiplicity. 

Olaf