18

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?

duplode
  • 33,731
  • 7
  • 79
  • 150
Petr
  • 62,528
  • 13
  • 153
  • 317

2 Answers2

13

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.

Bakuriu
  • 98,325
  • 22
  • 197
  • 231
dfeuer
  • 48,079
  • 5
  • 63
  • 167
  • 3
    You shouldn't use things like "update" or "edit" in a post. The edit history is more than enough to look at when something was changed/added. I took the liberty of removing them (but not the content) and moving the part that references the bug tracker at the top, so that it's more easily accessible. – Bakuriu Aug 24 '15 at 17:48
  • @Bakuriu Really? So, instead of just seeing immediately that something was changed, we're supposed to dig into edit history? Is the normal way just too simple? – MigMit Aug 24 '15 at 19:17
  • 3
    @MigMit The "normal way", as you call it, is **noise**. If I'm looking for an answer why should I read hundreds of lines of unrelated "edits" to end up with a 2 line answer in the end? Answer should maximize usefulness, which means being readable and easily accessible. Splitting information into various blocks isn't generally a good solution. It may be ok when the question/answer is still unclear/incomplete but once it's clear the content should be well organized. If someone is curious to see how it evolved he can look at the edit history, but that's metadata. – Bakuriu Aug 24 '15 at 19:23
  • 1
    @Bakuriu if I want an answer to my question, it's entirely possible that the first reply is not what I need. Later, when I revisit the page, I would normally skip the answers I've already seen — UNLESS there is a clear visual clue that SOMETHING has changed. The bold *Edit* provides such a clue. It's not *noise*, it's *information*, that makes using this page EASIER. – MigMit Aug 24 '15 at 19:41
  • 1
    Maybe we should transfer this discussion somewhere else? – MigMit Aug 24 '15 at 19:42
1

I believe that the representation itself was OK and that the lawfulness could have been remedied by changing these method signatures

iter :: Functor f => (f a -> a) -> ([a] -> a) -> Free f a -> a
iterM :: (Monad m, Functor f) => (f (m a) -> m a) -> ([m a] -> m a) -> Free f a -> m a

to

iter :: (Functor f, Monoid a) => (f a -> a) -> Free f a -> a
iterM :: (MonadPlus m, Functor f) => (f (m a) -> m a) -> Free f a -> m a

i.e.

  • use Monoid a instead of an arbitrary function [a] -> a in iter;
  • use MonadPlus m instead of an arbitrary function [m a] -> m a in iterM.

My guess is that it was removed (instead of fixed) just because it is not worth to keep around when FreeT f [] gives an equivalent representation.

Tomas Mikula
  • 6,537
  • 25
  • 39