haskellmonadsfree-monadmonadplus

What was wrong with Control.MonadPlus.Free?

The free MonadPlus defined as

data Free f a = Pure a | Free (f (Free f a)) | Plus [Free f a]

was removed in free 4.6 with the following remark (changelog):

Removed Control.MonadPlus.Free. Use FreeT f [] instead and the result will be law-abiding.

What was the problem, in particular, what laws didn't hold?

Solution

  • According to this issue in the bug tracker the old definition does not obey the associative law.

    Although I know little about such things, I suspect an other problem is redundancy:

    Pure a
Plus [Pure a]
Plus [Plus [Pure a]]
...

    all seem to represent the same thing. Free structures are generally supposed to be unique. There are times when they cannot be represented uniquely (e.g., free abelian groups) but when possible they should be.

    Actually, I think the suggested alternative suffers from the same problem, although it might be possible to repair it by using NonEmpty instead of []. So this change could just be a matter of removing excess cruft from the library.