haskell - ¿Qué estuvo mal con Control.MonadPlus.Free?

monads free-monad

Question

El MonadPlus libre definido como

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

fue eliminado en la versión 4.6 libre con el siguiente comentario ( changelog ):

Se ha eliminado Control.MonadPlus.Free . Utilice FreeT f [] lugar y el resultado será respetuoso de la ley.

¿Cuál fue el problema, en particular, qué leyes no se aplicaron?

Answer 1

Creo que la representación en sí estaba bien y que la legalidad podría haberse corregido cambiando las firmas de estos métodos.

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

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

es decir

• use Monoid a lugar de una función arbitraria [a] -> a en iter ;
• use MonadPlus m lugar de una función arbitraria [ma] -> ma en iterM .

Supongo que se eliminó (en lugar de repararlo) solo porque no vale la pena mantenerlo cuando FreeT f [] da una representación equivalente.

Answer 2

De acuerdo con este issue en el rastreador de errores, la definición anterior no obedece a la ley asociativa.

Aunque sé poco sobre estas cosas, sospecho que otro problema es la redundancia:

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

Todos parecen representar lo mismo. Generalmente se supone que las estructuras libres son únicas. Hay momentos en que no se pueden representar de forma única (por ejemplo, grupos abelianos libres), pero cuando sea posible, deberían estarlo.

En realidad, creo que la alternativa sugerida tiene el mismo problema, aunque podría ser posible repararla utilizando NonEmpty lugar de [] . Así que este cambio podría ser simplemente una cuestión de eliminar el exceso de cruft de la biblioteca.