monadas - monads haskell

Buenos ejemplos de Not a Functor/Functor/Applicative/Monad?

Question

Mientras le explico a alguien qué tipo de clase es X, me cuesta encontrar buenos ejemplos de estructuras de datos que sean exactamente X.

Por lo tanto, solicito ejemplos para:

• Un constructor de tipo que no es un Functor.
• Un constructor de tipo que es un Functor, pero no Aplicativo.
• Un constructor de tipo que es un Aplicativo, pero no es una Mónada.
• Un constructor de tipo que es una Mónada.

Creo que hay muchos ejemplos de Monad en todas partes, pero un buen ejemplo de Monad con alguna relación con ejemplos anteriores podría completar la imagen.

Busco ejemplos que sean similares entre sí, que difieran solo en aspectos importantes para pertenecer a la clase de tipo particular.

Si uno lograra obtener un ejemplo de Arrow en algún lugar de esta jerarquía (¿está entre Applicative y Monad?), ¡Eso también sería genial!

Answer 1

Creo que las otras respuestas omitieron algunos ejemplos simples y comunes:

Un constructor de tipo que es un Functor pero no un Aplicativo. Un simple ejemplo es un par:

instance Functor ((,) r) where
    fmap f (x,y) = (x, f y)

Pero no hay forma de cómo definir su instancia Applicative sin imponer restricciones adicionales sobre r . En particular, no hay forma de cómo definir pure :: a -> (r, a) para una r arbitraria.

Un constructor de tipo que es un Aplicativo, pero no es una Mónada. Un ejemplo bien conocido es ZipList . (Es un newtype que envuelve las listas y les proporciona una instancia Applicative diferente).

fmap se define de la manera habitual. Pero pure y <*> se definen como

pure x                    = ZipList (repeat x)
ZipList fs <*> ZipList xs = ZipList (zipWith id fs xs)

pure crea una lista infinita repitiendo el valor dado, y <*> comprime una lista de funciones con una lista de valores - aplica la i -ésima función al i -ésimo elemento. (El estándar <*> en [] produce todas las combinaciones posibles de aplicar la i -ésima función al j -ésimo elemento). Pero no hay una manera sensata de cómo definir una mónada (ver esta publicación ).

¿Cómo encajan las flechas en la jerarquía functor / aplicativo / mónada? Ver modismos son ajenos, las flechas son meticulosas, las mónadas son promiscuas por Sam Lindley, Philip Wadler, Jeremy Yallop. MSFP 2008. (Ellos llaman modismos de funcionamientos aplicativos.) El resumen:

Revisamos la conexión entre tres nociones de computación: las mónadas de Moggi, las flechas de Hughes y los modismos de McBride y Paterson (también llamados funtores aplicativos). Mostramos que los modismos son equivalentes a las flechas que satisfacen el tipo isomorfismo A ~> B = 1 ~> (A -> B) y que las mónadas son equivalentes a las flechas que satisfacen el tipo isomorfismo A ~> B = A -> (1 ~ > B). Además, las expresiones idiomáticas se insertan en flechas y flechas incrustadas en mónadas.

Answer 2

Me gustaría proponer un enfoque más sistemático para responder a esta pregunta, y también para mostrar ejemplos que no utilizan ningún truco especial como los valores "inferiores" o tipos de datos infinitos o algo por el estilo.

¿Cuándo los constructores de tipos no tienen instancias de clase de tipo?

En general, hay dos razones por las que un constructor de tipos podría no tener una instancia de una cierta clase de tipo:

1. No se pueden implementar las firmas de tipo de los métodos necesarios de la clase de tipo.
2. Puede implementar las firmas de tipo pero no puede satisfacer las leyes requeridas.

Los ejemplos del primer tipo son más fáciles que los del segundo tipo porque para el primer tipo, solo debemos verificar si se puede implementar una función con una firma de tipo determinada, mientras que para el segundo tipo, se requiere que demuestremos que no hay implementación posiblemente podría satisfacer las leyes.

Ejemplos específicos

• Un constructor de tipos que no puede tener una instancia de tipo funtor porque no se puede implementar el tipo:

data F a = F (a -> Int)

Este es un contrafunctor, no un funtor, porque usa el parámetro tipo a en una posición contravariante. Es imposible implementar una función con firma de tipo (a -> b) -> F a -> F b .

• Un constructor de tipos que no es un functor legal aunque se puede implementar la firma de tipo de fmap :

data Q a = Q(a -> Int, a) fmap :: (a -> b) -> Q a -> Q b fmap f (Q(g, x)) = Q(/_ -> gx, fx) -- this fails the functor laws!

El aspecto curioso de este ejemplo es que podemos implementar fmap del tipo correcto aunque F no puede ser un funtor porque usa a en una posición contravariante. Entonces, esta implementación de fmap mostrada arriba es engañosa, aunque tiene la firma de tipo correcta (creo que esta es la única implementación posible de esa firma de tipo), las leyes de functor no están satisfechas (esto requiere algunos cálculos simples para verificar).

De hecho, F es solo un profundoctor, no es un functor ni un contrafunctor.

• Un functor legal que no es aplicable porque no se puede implementar la firma tipo de pure : tome la mónada Writer (a, w) y elimine la restricción que w debería ser un monoide. Entonces es imposible construir un valor de tipo (a, w) partir de a .

• Un funtor que no es aplicable porque la firma de tipo de <*> no puede implementarse: data F a = Either (Int -> a) (String -> a) .

• Un functor que no es un aplicativo legal aunque los métodos de clase de tipo se pueden implementar:

data P a = P ((a -> Int) -> Maybe a)

El constructor de tipo P es un funtor porque usa a solo en posiciones covariantes.

instance Functor P where
   fmap :: (a -> b) -> P a -> P b
   fmap fab (P pa) = P (/q -> fmap fab $ pa (q . fab))

La única implementación posible de la firma de tipo de <*> es una función que siempre devuelve Nothing :

 (<*>) :: P (a -> b) -> P a -> P b
 (P pfab) <*> (P pa) = /_ -> Nothing  -- fails the laws!

Pero esta implementación no satisface la ley de identidad para los funtores aplicativos.

• Un functor que es Applicative pero no una Monad porque la firma tipo de bind no se puede implementar.

¡No conozco ninguno de esos ejemplos!

• Un funtor que es aplicable pero no una Monad porque las leyes no se pueden cumplir aunque se pueda implementar la firma tipo de bind .

Este ejemplo ha generado bastante debate, por lo que es seguro decir que probar este ejemplo correcto no es fácil. Pero varias personas lo han verificado de forma independiente por diferentes métodos. Consulte Is `data PoE a = Empty | Par aa` una mónada? para una discusión adicional.

 data B a = Maybe (a, a)
   deriving Functor

 instance Applicative B where
   pure x = Just (x, x)
   b1 <*> b2 = case (b1, b2) of
     (Just (x1, y1), Just (x2, y2)) -> Just((x1, x2), (y1, y2))
     _ -> Nothing

Es algo engorroso probar que no hay una instancia legítima de Monad . La razón del comportamiento no monádico es que no existe una forma natural de implementar bind cuando una función f :: a -> B b podría devolver Nothing o Just para diferentes valores de a .

Tal vez sea más claro considerar Maybe (a, a, a) , que tampoco es una mónada, y tratar de implementar join para eso. Uno encontrará que no existe una forma intuitiva razonable de implementar join .

 join :: Maybe (Maybe (a, a, a), Maybe (a, a, a), Maybe (a, a, a)) -> Maybe (a, a, a)
 join Nothing = Nothing
 join Just (Nothing, Just (x1,x2,x3), Just (y1,y2,y3)) = ???
 join Just (Just (x1,x2,x3), Nothing, Just (y1,y2,y3)) = ???
 -- etc.

En los casos indicados por ??? , parece claro que no podemos producir Just (z1, z2, z3) de ninguna manera razonable y simétrica a partir de seis valores diferentes de tipo a . Ciertamente podríamos elegir algún subconjunto arbitrario de estos seis valores, por ejemplo, siempre tomar el primer no vacío Maybe , pero esto no satisfaría las leyes de la mónada. La devolución de Nothing tampoco cumplirá las leyes.

• Una estructura de datos similar a un árbol que no es una mónada aunque tiene asociatividad para bind , pero no cumple con las leyes de identidad.

La mónada de árbol típica (o "un árbol con ramas en forma de functor") se define como

 data Tr f a = Leaf a | Branch (f (Tr f a))

Esta es una mónada gratuita sobre el funtor f . La forma de los datos es un árbol donde cada punto de ramificación es un "functorful" de subárboles. El árbol binario estándar se obtendría con el type fa = (a, a) .

Si modificamos esta estructura de datos haciendo también las hojas en la forma del funtor f , obtenemos lo que llamo un "semimonad" - tiene un bind que satisface la naturalidad y las leyes de asociatividad, pero su método pure falla uno de la identidad leyes "Semimonads son semigrupos en la categoría de endofunctors, ¿cuál es el problema?" Este es el tipo clase Bind .

Para simplificar, defino el método join lugar de bind :

 data Trs f a = Leaf (f a) | Branch (f (Trs f a))
 join :: Trs f (Trs f a) -> Trs f a
 join (Leaf ftrs) = Branch ftrs
 join (Branch ftrstrs) = Branch (fmap @f join ftrstrs)

El injerto de rama es estándar, pero el injerto de hoja no es estándar y produce una Branch . Esto no es un problema para la ley de asociatividad, pero infringe una de las leyes de identidad.

¿Cuándo los tipos de polinomios tienen instancias de mónada?

Ninguno de los funtores Maybe (a, a) y Maybe (a, a, a) pueden recibir una instancia legítima de Monad , aunque obviamente son Applicative .

Estos funtores no tienen trucos, no hay Void o bottom ninguna bottom , no hay pereza / rigor complicados, no hay estructuras infinitas y no hay restricciones de clases de tipos. La instancia Applicative es completamente estándar. Las funciones return y bind se pueden implementar para estos funtores pero no satisfarán las leyes de la mónada. En otras palabras, estos funtores no son mónadas porque falta una estructura específica (pero no es fácil entender qué es exactamente lo que falta). Como ejemplo, un pequeño cambio en el funtor puede convertirlo en una mónada: data Maybe a = Nothing | Just a data Maybe a = Nothing | Just a es una mónada. Otro data P12 a = Either a (a, a) functor similar data P12 a = Either a (a, a) también es una mónada.

Construcciones para mónadas polinomiales

En general, aquí hay algunas construcciones que producen Monad lícitas fuera de tipos polinomiales. En todas estas construcciones, M es una mónada:

1. type M a = Either c (w, a) donde w es cualquier monoide
2. type M a = m (Either c (w, a)) donde m es cualquier mónada y w es cualquier monoide
3. type M a = (m1 a, m2 a) donde m1 y m2 son cualquier mónada
4. type M a = Either a (ma) donde m es cualquier mónada

La primera construcción es WriterT w (Either c) , la segunda construcción es WriterT w (EitherT cm) . La tercera construcción es un producto componente de mónadas: pure @M se define como el producto componente de pure @m1 y pure @m2 , y join @M se define omitiendo datos de productos cruzados (p. Ej. m1 (m1 a, m2 a) se mapea a m1 (m1 a) omitiendo la segunda parte de la tupla):

 join :: (m1 (m1 a, m2 a), m2 (m1 a, m2 a)) -> (m1 a, m2 a)
 join (m1x, m2x) = (join @m1 (fmap fst m1x), join @m2 (fmap snd m2x))

La cuarta construcción se define como

 data M m a = Either a (m a)
 instance Monad m => Monad M m where
    pure x = Left x
    join :: Either (M m a) (m (M m a)) -> M m a
    join (Left mma) = mma
    join (Right me) = Right $ join @m $ fmap @m squash me where
      squash :: M m a -> m a
      squash (Left x) = pure @m x
      squash (Right ma) = ma

He comprobado que las cuatro construcciones producen mónadas legales.

Conjeturo que no hay otras construcciones para las mónadas polinomiales. Por ejemplo, el functor Maybe (Either (a, a) (a, a, a, a)) no se obtiene a través de ninguna de estas construcciones y, por lo tanto, no es monádico. Sin embargo, Either (a, a) (a, a, a) es monádico porque es isomorfo al producto de tres mónadas a , a , y Maybe a . Además, Either (a,a) (a,a,a,a) es monádico porque es isomorfo al producto de a y Either a (a, a, a) .

Las cuatro construcciones que se muestran arriba nos permitirán obtener cualquier suma de cualquier cantidad de productos de cualquier número de '' a '', por ejemplo, Either (Either (a, a) (a, a, a, a)) (a, a, a, a, a)) y así sucesivamente. Todos los constructores de dichos tipos tendrán (al menos una) instancia de Monad .

Queda por ver, por supuesto, qué casos de uso pueden existir para tales mónadas. Otro problema es que las instancias de Monad derivadas a través de las construcciones 1-4 no son en general únicas. Por ejemplo, el tipo constructor type F a = Either a (a, a) puede darse una instancia de Monad de dos maneras: por construcción 4 usando la mónada (a, a) , y por construcción 3 usando el tipo isomorfismo Either a (a, a) = (a, Maybe a) . Nuevamente, encontrar casos de uso para estas implementaciones no es inmediatamente obvio.

Queda una pregunta: dado un tipo de datos polinomiales arbitrarios, cómo reconocer si tiene una instancia de Monad . No sé cómo probar que no hay otras construcciones para las mónadas polinomiales. No creo que haya ninguna teoría hasta ahora para responder esta pregunta.

Answer 3

Mi estilo puede ser limitado por mi teléfono, pero aquí va.

newtype Not x = Kill {kill :: x -> Void}

no puede ser un Functor. Si lo fuera, tendríamos

kill (fmap (const ()) (Kill id)) () :: Void

y la Luna estaría hecha de queso verde.

mientras tanto

newtype Dead x = Oops {oops :: Void}

es un funtor

instance Functor Dead where
  fmap f (Oops corpse) = Oops corpse

pero no puede ser aplicativo, o tendríamos

oops (pure ()) :: Void

y Green estaría hecho de queso Moon (que en realidad puede suceder, pero solo más tarde en la noche).

(Nota adicional: Data.Void , como en Data.Void es un tipo de datos vacío. Si intentas usar undefined para demostrar que es un Monoid, unsafeCoerce para demostrar que no es así).

Alegremente

newtype Boo x = Boo {boo :: Bool}

es aplicativo de muchas maneras, por ejemplo, como lo tendría Dijkstra,

instance Applicative Boo where
  pure _ = Boo True
  Boo b1 <*> Boo b2 = Boo (b1 == b2)

pero no puede ser una Mónada. Para ver por qué no, observe que el retorno debe ser constantemente Boo True o Boo False , y de ahí que

join . return == id

no puede sostenerse.

Oh sí, casi lo olvido

newtype Thud x = The {only :: ()}

es una Mónada Tira el tuyo.

Avión para atrapar ...

Answer 4

Un buen ejemplo para un constructor de tipos que no es un funtor es Set : No puede implementar fmap :: (a -> b) -> fa -> fb , porque sin una restricción adicional Ord b no puede construir fb .

Answer 5

Un constructor de tipo que no es un Functor:

newtype T a = T (a -> Int)

Puede hacer un functor contravariante fuera de él, pero no un functor (covariante). Intenta escribir fmap y fmap . Tenga en cuenta que la versión de functor contravariante está invertida:

fmap      :: Functor f       => (a -> b) -> f a -> f b
contramap :: Contravariant f => (a -> b) -> f b -> f a

Un constructor de tipo que es un funtor, pero no Aplicativo:

No tengo un buen ejemplo. Está Const , pero idealmente me gustaría un concreto no monoide y no puedo pensar en ninguno. Todos los tipos son básicamente numéricos, enumeraciones, productos, sumas o funciones cuando se llega a él. Puede ver abajo a un trabajador porcino y estoy en desacuerdo sobre si Data.Void es un Monoid ;

instance Monoid Data.Void where
    mempty = undefined
    mappend _ _ = undefined
    mconcat _ = undefined

Como _|_ es un valor legal en Haskell, y de hecho el único valor legal de Data.Void , cumple con las reglas de Data.Void . No estoy seguro de qué tiene que ver con unsafeCoerce insegura, ya que su programa ya no garantiza que no viole la semántica de Haskell tan pronto como use cualquier función unsafe .

Consulte el Haskell Wiki para obtener un artículo sobre las funciones de abajo ( link ) o inseguras ( link ).

Me pregunto si es posible crear ese tipo de constructor usando un sistema de tipo más rico, como Agda o Haskell con varias extensiones.

Un constructor de tipo que es un Aplicativo, pero no una Mónada:

newtype T a = T {multidimensional array of a}

Puede hacer un aplicativo de esto, con algo como:

mkarray [(+10), (+100), id] <*> mkarray [1, 2]
  == mkarray [[11, 101, 1], [12, 102, 2]]

Pero si lo convierte en una mónada, podría obtener un desajuste de dimensión. Sospecho que ejemplos como este son raros en la práctica.

Un constructor de tipo que es una Mónada:

[]

Acerca de Arrows:

Preguntar dónde se encuentra una flecha en esta jerarquía es como preguntar qué tipo de forma es "rojo". Tenga en cuenta el desajuste de tipo:

Functor :: * -> *
Applicative :: * -> *
Monad :: * -> *

pero,

Arrow :: * -> * -> *