haskell - quiere - neo monadología
¿Puede una mónada ser una comada? (5)
Sé lo que es una mónada. Creo que correctamente he envuelto mi mente en torno a lo que es un comonad. (O más bien, lo que uno es parece bastante simple; la parte difícil es comprender qué es útil acerca de esto ...)
Mi pregunta es: ¿Puede algo ser una mónada y una comuna?
Preveo dos posibles respuestas:
- Sí, esto es común y ampliamente útil.
- No, hacen trabajos tan diferentes que no habría razón para querer que ambas cosas sean ambas.
Entonces, ¿cuál es?
Ampliando la sugerencia de Hammer, parece lo suficientemente simple como para escribir una función [x] -> [[x]] . Por ejemplo,
map (/ x -> [x])
funcionaría bien Así que parece que las listas podrían formar un comonad. Ah, pero espera. Eso maneja cojoin , pero ¿qué pasa con coreturn :: [x] -> x ? Esto , presumiblemente, es la razón por la cual solo las listas no vacías forman un comonad.
Esto nos da una función Cobind con el tipo ([x] -> x) -> [x] -> [x] . Curiosamente, Hoogle no conoce tal función. Y, sin embargo, ya tenemos concatMap :: (x -> [x]) -> [x] -> [x] . No estoy viendo un uso inmediato para la función Cobind, pero puedo imaginar una existente.
Todavía estoy tratando de envolver mi mente en torno a Comonad y para qué podría ser útil. Las respuestas hasta ahora me han dado algo en que pensar ...
Depende de lo que consideres una "mónada". Si pregunta "¿es posible que un tipo sea una instancia de Monad y Comonad a la vez?" entonces sí. Aquí hay un ejemplo trivial.
newtype Id a = Id a
instance Monad Identity where
return = Id
(Id a) >>= f = f a
instance Comonad Identity where
extract (Id a) = a
extend f ida = Id (f ida)
Si lo dice matemáticamente, entonces una mónada es un triple (X, return, bind) donde X es un tipo y el return y el bind siguen los tipos y las leyes que espera. De manera similar, un comonad es (X, extend, extract) . Acabo de demostrar que las X pueden ser las mismas, pero como los tipos de extend y return o extract y bind son diferentes, no es posible que tengan las mismas funciones. Así que una mónada matemática nunca puede ser una comuna.
El Cofree Comonad produce algunas estructuras de datos que son útiles tanto para las Mónadas como para los Comonads:
data Cofree f a = a :< f (Cofree f a)
Cada Cofree Comonad sobre un funtor alternativo produce una Mónada; vea la instancia aquí:
http://hackage.haskell.org/packages/archive/free/3.4.1/doc/html/Control-Comonad-Cofree.html
instance Alternative f => Monad (Cofree f) where
return x = x :< empty
(a :< m) >>= k = case k a of
b :< n -> b :< (n <|> fmap (>>= k) m)
Esto nos da, por ejemplo, listas no vacías como Mónadas y Comandas (junto con árboles no vacíos de ramas F, etc.).
Identity no es una alternativa, pero Cofree Identity produce un flujo infinito, y de hecho podemos dar una instancia de mónada diferente a ese flujo:
http://hackage.haskell.org/packages/archive/streams/3.1/doc/html/Data-Stream-Infinite.html
data Stream a = a :> Stream a
instance Comonad Stream where
duplicate = tails
extend f w = f w :> extend f (tail w)
extract = head
instance Monad Stream where
return = repeat
m >>= f = unfold (/(bs :> bss) -> (head bs, tail <$> bss)) (fmap f m)
(tenga en cuenta que las funciones anteriores no están en las listas, sino que están definidas en el paquete de streams ).
De manera similar, la flecha del lector no es una alternativa, pero Cofree ((->) r) produce una máquina de Moore, y las máquinas de Moore también son mónadas y comadas.
http://hackage.haskell.org/packages/archive/machines/0.2.3.1/doc/html/Data-Machine-Moore.html
data Moore a b = Moore b (a -> Moore a b)
instance Monad (Moore a) where
return a = r where r = Moore a (const r)
Moore a k >>= f = case f a of
Moore b _ -> Moore b (k >=> f)
_ >> m = m
instance Comonad (Moore a) where
extract (Moore b _) = b
extend f w@(Moore _ g) = Moore (f w) (extend f . g)
Entonces, ¿cuál es la intuición detrás de todos estos ejemplos? Bueno conseguimos las operaciones comonádicas de forma gratuita. Las operaciones monádicas que obtenemos son todas formas de diagonalización. Con la alternativa, podemos <|> juntar las cosas para "embellecer" la estructura y hacer que las cosas "vacías" se conviertan en mágicas cuando nos quedamos sin estructura. Esto nos permite trabajar en casos finitos. A falta de una alternativa, necesitamos tener una cantidad indefinida de estructura, de modo que no importa cuántas operaciones de "unión" (que podemos pensar como empalme o sustitución) que hacemos, siempre hay más espacio para colocar los elementos empalmados (como en el Hotel Hilbert: http://www.encyclopediaofmath.org/index.php/Hilbert_infinite_hotel ).
En relación, cada Comonad da lugar a una Mónada relacionada (aunque considero que esto es más una curiosidad):
http://hackage.haskell.org/packages/archive/kan-extensions/3.1.1/doc/html/Control-Monad-Co.html
Hay muchas estructuras interesantes que son a la vez una Monad y una Comonad .
El funtor de Identity ha sido señalado aquí por varias otras personas, pero hay ejemplos no triviales.
The Writer Monad desempeña un papel de Reader como Comonad .
instance Monoid e => Monad ((,) e)
instance Comonad ((,) e)
El Reader Monad desempeña un papel similar a un Writer como Comonad .
instance Monad ((->) e)
instance Monoid e => Comonad ((->)e)
Las listas que no están vacías también forman una mónada y una coma y, de hecho, son un caso especial de una construcción más grande que involucra comonadas de cofree. El caso de Identity también puede ser visto como un caso especial de esto.
También hay varias construcciones similares a Yoneda y Codensity basadas en extensiones de Kan, que trabajan para transformar mónadas y comonads, aunque favorecen una u otra en términos de eficiencia operativa.
También tengo un adaptador que convierte una combinación arbitraria en un transformador de mónada. Lamentablemente la conversión opuesta no es posible en Haskell.
En el álgebra lineal hay una noción de una bialgebra . Idealmente, si tenemos algo que forma una Monad y un Comonad y queremos usar esas operaciones juntas sin razonar caso por caso, a uno le gustaría tener esa return y join son las coalgebras de Comonad y por extensión ese extract duplicate son álgebras de la Monad . Si esas condiciones se mantienen, entonces realmente puede razonar sobre el código que tiene restricciones tanto de Comonad f como de Comonad f y mezcla los combinadores de cada uno sin el razonamiento caso por caso.
Sí. Convirtiendo algunos comentarios en una respuesta:
newtype Identity a = Identity {runIdenity :: a} deriving Functor
instance Monad Identity where
return = Identity
join = runIdentity
instance CoMonad Identity where
coreturn = runIdentity
cojoin = Identity
Reader y Writer son duales exactos, como lo muestra
class CoMonoid m where
comempty :: (m,a) -> a
comappend :: m -> (m,m)
--every haskell type is a CoMonoid
--that is because CCCs are boring!
instance Monoid a => Monad ((,) a) where
return x = (mempty,x)
join (a,(b,x)) = (a <> b, x)
instance CoMonoid a => CoMonad ((,) a) where
coreturn = comempty
cojoin = associate . first comappend
instance CoMonoid a => Monad ((->) a) where
return = flip (curry comempty)
join f = uncurry f . comappend
instance Monoid a => CoMonad ((->) a) where
coreturn f = f mempty
cojoin f a b = f (a <> b)