25

I've seen mentioned that

ListT is a classic example of a buggy monad transformer that doesn't satisfy the monad laws.

Can this be demonstrated by a simple example?

Edit: My idea with ListT [] is a bit wrong, I missed that the documentation requires the inner monad to be commutative. So, is ListT buggy just in the sense that has this requirement, or is there another problem? (The examples at Haskell wiki all use ListT IO and IO is obviously not commutative.)

Petr
  • 62,528
  • 13
  • 153
  • 317

1 Answers1

20

A simple example that shows how it fails the associativity law:

v :: Int -> ListT [] Int
v 0 = ListT [[0, 1]]
v 1 = ListT [[0], [1]]

main = do
    print $ runListT $ ((v >=> v) >=> v) 0
    -- = [[0,1,0,0,1],[0,1,1,0,1],[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1]]
    print $ runListT $ (v >=> (v >=> v)) 0
    -- = [[0,1,0,0,1],[0,1,0,0],[0,1,0,1],[0,1,1,0,1],[0,1,1,0],[0,1,1,1]]

More examples (mostly using IO) and a solution how to fix ListT can be found at ListT done right.

Petr
  • 62,528
  • 13
  • 153
  • 317
  • 2
    The documentation says that the transformed monad must be commutative; try it with e.g. `v n = ListT $ map (read :: String -> Int) . permutations . show . (+n)` – applicative Sep 27 '12 at 15:51
  • 1
    @applicative Good point, I missed that. I tried with the `(->)` monad, but so far I couldn't find a counter-example. – Petr Sep 27 '12 at 16:40
  • 11
    Well... they're called "monad transformers", not "commutative monad transformers". If I defined a transformer that only worked correctly when applied to a few specific monads, would anyone consider that satisfactory? – C. A. McCann Sep 27 '12 at 17:52
  • 3
    @C.A.McCann True. What puzzles me that even though the problems with `ListT` are known and there is even a proposed solution ([ListT done right](http://www.haskell.org/haskellwiki/ListT_done_right)) it still remains in this form in the Haskell's standard library. – Petr Sep 27 '12 at 19:18
  • 3
    Versions of `ListT` along those lines fail to properly capture many uses of `[]`, though--specifically, uses where a list is treated as a multiset instead of a sequence, i.e., finite lists where the order of elements doesn't matter. And of course that's precisely the problem--the broken `ListT` assumes that the order of `(>>=)` applications in the inner monad doesn't matter either, while the "done right" version inserts the wrapped monad at each step in a (possibly infinite) stream. The latter captures the "list as control structure" idea, and as such is related to iteratee-ish streams. – C. A. McCann Sep 27 '12 at 20:27
  • 1
    @applicative There is an important difference. `ListT` gives restrictions on the inner monad. `WriterT` has no such restriction, it restricts its `w` type parameter to be `Monoid`, but it has nothing to do with the inner monad. So if `w` is a monoid, you can apply `WriterT w` to any monad (unlike `ListT`). – Petr Sep 27 '12 at 20:52
  • 1
    Sorry I deleted my comment while trying to improve it. I was first agreeing that `ListT` is pointless, but suggesting that the restriction to commutative monads is no more alarming than the restriction of e.g. the claim that `WriterT` a is a monad transformer to the case where a is a monoid. The only difference is that there are not `MonadCommutative` and `MonadCommutativeTrans` classes. This would answer every theoretical objection. It would be quite tiresome since they would have exactly the same methods but an additional proof obligation, which could only be stated in the documentation. – applicative Sep 27 '12 at 21:16
  • 2
    @applicative Yes, adding such a class would be helpful. We could simply have `class Monad m => MonadCommutative m` (and the same for `MonadTrans`) with no additional methods. Then any commutative methods would be simply marked by this class. – Petr Sep 28 '12 at 06:45
  • @C.A.McCann, I realize this is a while after you wrote that comment, but: I'm reading you to be saying that LogicT and ListT-done-right and such aren't suitable implementations for a multiset. Can you explain that? I don't see why they wouldn't be. Granted, I'm primarily thinking of LogicT and maybe the two alternatives I cited differ in some important way I'm not now attending to. And granted also, if one wants a multiset then an implementation using [ ] and the standard ListT aren't broken (in the way described here). – dubiousjim Sep 22 '16 at 12:45