Что было не так с Control.MonadPlus.Free?

Question

Бесплатный MonadPlus определяется как

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

был удален в бесплатной версии 4.6 со следующим замечанием ( changelog):

Удалены Control.MonadPlus.Free, использование FreeT f [] вместо этого и результат будет законопослушным.

В чем заключалась проблема, в частности, какие законы не выполнялись?

Answer 1

Согласно этой проблеме в багтрекере старое определение не подчиняется ассоциативному закону.

---

Хотя я мало знаю о таких вещах, я подозреваю, что другая проблема заключается в избыточности:

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

похоже, все они представляют одно и то же. Свободные структуры, как правило, должны быть уникальными. Есть моменты, когда они не могут быть представлены однозначно (например, свободные абелевы группы), но когда это возможно, они должны быть.

На самом деле, я думаю, что предлагаемая альтернатива страдает той же проблемой, хотя ее можно исправить, используя NonEmpty вместо [], Таким образом, это изменение может быть просто вопросом удаления лишней кучи из библиотеки.

Answer 2

Я считаю, что само представление было в порядке, и что законность могла быть исправлена ​​путем изменения этих сигнатур методов

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

в

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

т.е.

• использование Monoid a вместо произвольной функции [a] -> a в iter;
• использование MonadPlus m вместо произвольной функции [m a] -> m a в iterM,

Я предполагаю, что он был удален (а не исправлен) только потому, что его не стоит хранить, когда FreeT f [] дает эквивалентное представление.