[Haskell-cafe] ListT version leveraging Traversable
Olaf Klinke
olf at aatal-apotheke.de
Mon Feb 3 21:03:18 UTC 2020
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
More information about the Haskell-Cafe
mailing list