Что случилось с Control.MonadPlus.Free?

бесплатный MonadPlus, определенный как

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

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

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

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

Ответ 1

В соответствии с этим issue в трекере ошибок старое определение не подчиняется ассоциативному закону.

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

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

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

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

Ответ 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 [] дает эквивалентное представление.