haskell - category theory for programmers

¿Diferencia entre mónadas libres y puntos de referencia de funtores?

Question

Estaba leyendo http://www.haskellforall.com/2013/06/from-zero-to-cooperative-threads-in-33.html donde se deriva un árbol sintáctico abstracto como la mónada libre de un functor que representa un conjunto de instrucciones. Noté que la mónada gratuita Free no es muy diferente del operador de punto fijo en Functors Fix .

El artículo usa las operaciones de mónada y sintaxis para construir esos AST (puntos de referencia) de forma concisa. Me pregunto si ese es el único beneficio de la instancia de la mónada gratuita. ¿Hay alguna otra aplicación interesante que permita?

Answer 1

(Nota: esto combina un poco de los comentarios de la mina y @ Gabriel arriba).

Es posible que cada habitante del punto de edición Functor de un Functor sea ​​infinito, es decir, que sea let x = (Fix (Id x)) in x === (Fix (Id (Fix (Id ...)))) es el único habitante de Fix Identity . Free difiere inmediatamente de Fix en que asegura que hay al menos un habitante finito de Free f . De hecho, si Fix f tiene habitantes infinitos, Free f tiene infinitamente muchos habitantes finitos.

Otro efecto secundario inmediato de esta falta de límites es que Functor f => Fix f ya no es un Functor . Tendríamos que implementar fmap :: Functor f => (a -> b) -> (fa -> fb) , pero Fix ha "llenado todos los agujeros" en fa que solía contener el a , entonces ya no tiene alguna para aplicar nuestra función fmap ''d.

Esto es importante para crear Monad s porque nos gustaría implementar return :: a -> Free fa y tener, por ejemplo, esta ley, mantener fmap f . return = return . f fmap f . return = return . f fmap f . return = return . f , pero ni siquiera tiene sentido en un Functor f => Fix f .

Entonces, ¿cómo "arregla" Free estas debilidades del punto de edición? "Aumenta" nuestro functor base con el constructor Pure . Por lo tanto, para todo Functor f , Pure :: a -> Free fa . Este es nuestro habitante garantizado para ser finito del tipo. También de inmediato nos da una definición de return buen comportamiento.

return = Pure

Por lo tanto, puede pensar en esta adición como eliminar un "árbol" potencialmente infinito de funcionamientos anidados creados por Fix y mezclar en un cierto número de yemas "vivientes", representadas por Pure . Creamos nuevos brotes utilizando return que podrían interpretarse como una promesa de "devolver" a ese brote más tarde y agregar más cómputos. De hecho, eso es exactamente lo que hace flip (>>=) :: (a -> Free fb) -> (Free fa -> Free fb) . Dada una función de "continuación" f :: a -> Free fb que se puede aplicar a los tipos a , recurrimos a nuestro árbol volviendo a cada Pure a y reemplazándolo con la continuación calculada como fa . Esto nos permite "crecer" nuestro árbol.

Ahora, Free es claramente más general que Fix . Para conducir esta casa, es posible ver cualquier tipo Functor f => Fix f como un subtipo del correspondiente Free fa ! Simplemente elija a ~ Void donde tenemos data Void = Void Void (es decir, un tipo que no se puede construir, es el tipo vacío, no tiene instancias).

Para hacerlo más claro, podemos romper nuestro Fix ''d Functor s con break :: Fix f -> Free fa y luego tratar de invertirlo con affix :: Free f Void -> Fix f .

break (Fix f) = Free (fmap break f) 
affix (Free f) = Fix (fmap affix f)

Note primero que affix no necesita manejar el caso Pure x porque en este caso x :: Void y por lo tanto no puede estar realmente allí, entonces Pure x es absurdo y lo ignoraremos.

También tenga en cuenta que el tipo de devolución de break es un poco sutil ya que el tipo a aparece solo en el tipo de devolución, Free fa , de modo que es completamente inaccesible para cualquier usuario de break . "Completamente inaccesible" y "no se puede crear una instancia" nos dan la primera pista de que, a pesar de los tipos, affix y break son inversos, pero podemos probarlo.

(break . affix) (Free f)
===                                     [definition of affix]
break (Fix (fmap affix f))
===                                     [definition of break]
Free (fmap break (fmap affix f))
===                                     [definition of (.)]
Free ( (fmap break . fmap affix) f )
===                                     [functor coherence laws]
Free (fmap (break . affix) f)

que debería mostrar (co-inductivamente, o simplemente de manera intuitiva , tal vez) que (break . affix) es una identidad. La otra dirección pasa de una manera completamente idéntica.

Entonces, con suerte, esto muestra que Free f es más grande que Fix f para todo Functor f .

Entonces, ¿por qué usar Fix ? Bueno, a veces solo quieres las propiedades de Free f Void debido a algún efecto secundario de la estratificación f s. En este caso, llamarlo Fix f deja en claro que no debemos intentar (>>=) o fmap sobre el tipo. Además, dado que Fix es solo un newtype , podría ser más fácil para el compilador "compilar" capas de Fix ya que solo juega un rol semántico.

• Nota: podemos hablar más formalmente sobre cómo Void y forall a. a forall a. a son tipos isomorfos para ver con mayor claridad cómo los tipos de affix y break son armoniosos. Por ejemplo, tenemos absurd :: Void -> a como absurd (Void v) = absurd v y no unabsurd :: (forall a. a) -> Void como no unabsurd a = a . Pero estos se ponen un poco tontos.

Answer 2

Hay una conexión profunda y ''simple''.

Es una consecuencia del teorema del funtor adjunto , los adjuntos a la izquierda conservan los objetos iniciales: L 0 ≅ 0 .

Categóricamente, Free f es un funtor de una categoría a sus álgebras F ( Free f se deja adjunta a un functor olvidadizo yendo al revés). Trabajando en Hask nuestro álgebra inicial es nula

Free f Void ≅ 0

y el álgebra inicial en la categoría de F-álgebras es Fix f : Free f Void ≅ Fix f

import Data.Void
import Control.Monad.Free

free2fix :: Functor f => Free f Void -> Fix f
free2fix (Pure void) = absurd void
free2fix (Free body) = Fix (free2fix <$> body)

fixToFree :: Functor f => Fix f -> Free f Void
fixToFree (Fix body) = Free (fixToFree <$> body)

De manera similar, los adjuntos correctos ( Cofree f , un funtor de Hask a la categoría de álgebras de F- co ) conservan los objetos finales: R 1 ≅ 1 .

En Hask esta es la unidad: () y el objeto final de F- co álgebras también es Fix f (que coinciden en Hask ) por lo que obtenemos: Cofree f () ≅ Fix f

import Control.Comonad.Cofree

cofree2fix :: Functor f => Cofree f () -> Fix f
cofree2fix (() :< body) = Fix (cofree2fix <$> body)

fixToCofree :: Functor f => Fix f -> Cofree f ()
fixToCofree (Fix body) = () :< (fixToCofree <$> body)

¡Mira qué similares son las definiciones!

newtype Fix f 
  = Fix (f (Fix f))

Fix f es Free f sin variables.

data Free f a 
  = Pure a 
  | Free (f (Free f a))

Fix f es Cofree f con valores ficticios.

data Cofree f a 
  = a <: f (Cofree f a)