haskell - ¿Hay algo llamado "semi-monad" o "contra-monad"?

monads category-theory

Question

Bueno, estoy estudiando Haskell Monads. Cuando leí el artículo de la teoría de categorías de Wikilibros, descubrí que la firma de los morfismos de la mónada se parece bastante a las tautologías en la lógica, pero es necesario convertir M a a ~~A , aquí ~ es la negación de la lógica.

return :: a -> M a -- Map to tautology A => ~~A, double negation introduction
(>>=) :: M a -> (a -> M b) -> M b -- Map to tautology ~~A => (A => ~~B) => ~~B

Las otras operaciones son también tautologías:

fmap :: (a -> b) -> M a -> M b -- Map to (A => B) -> (~~A => ~~B)
join :: M (M a) -> M a -- Map to ~~(~~A) => ~~A

También se entiende que de acuerdo con el hecho de que la correspondencia Curry-Howard de los lenguajes funcionales normales es la lógica intuitiva, no la lógica clásica, no podemos esperar una tautología como ~~A => A puede tener una correspondencia.

Pero estoy pensando en otra cosa. ¿Por qué la Mónada solo puede relacionarse con una doble negación? ¿Cuál es la correspondencia de negación única? Esto me llevó a la siguiente definición de clase:

class Nomad n where
    rfmap :: (a -> b) -> n b -> n a
    dneg :: a -> n (n a)

return :: Nomad n => a -> n (n a)
return = dneg
(>>=) :: Nomad n => n (n a) -> (a -> n (n b)) -> n (n b)
x >>= f = rfmap dneg $ rfmap (rfmap f) x

Aquí definí un concepto llamado "Nómada", y admite dos operaciones (ambas relacionadas con un axioma lógico en lógica intuitiva). Observe que el nombre "rfmap" significa el hecho de que su firma es similar al fmap del fmap , pero el orden de a y b se invierte en el resultado. Ahora puedo redefinir las operaciones de Monad con ellos, con reemplazar M a a n (na) .

Así que ahora vamos a la parte de la pregunta. El hecho de que Monad sea un concepto de la teoría de categorías parece significar que mi "Nómada" es también un concepto de teoría de categorías. ¿Así que qué es lo? ¿Es útil? ¿Hay trabajos o resultados de investigación en este tema?

Answer 1

Eso sería un funtor contravariante autoadjunto. rfmap proporciona la parte del funtor contravariante, y dneg es la unidad y el contable de la adjunción.

Op r es un ejemplo, que crea la mónada de continuación. Consulte los módulos contravariantes en http://hackage.haskell.org/package/adjunctions para obtener algunos códigos.

Debes leer link , que está relacionado y es muy interesante.

Answer 2

La doble negación es una mónada particular.

data Void --no constructor because it is uninhabited

newtype DN a = DN {runDN :: (a -> Void) -> Void}

instance Monad DN where
   return x = DN $ /f -> f x
   m >>= k  = DN $ /c -> runDN m (/a -> runDN (k a) c))

En realidad, este es un ejemplo de una mónada más general.

type DN = Cont Void
newtype Cont r a = Cont {runCont :: (a -> r) -> r}

que es la mónada para la continuación del paso.

Un concepto como "mónada" no se define solo por una firma, sino también por algunas leyes. Entonces, aquí hay una pregunta, ¿cuáles deberían ser las leyes para su construcción?

(a -> b) -> f b -> f a

Es la firma de un método bien conocido por la teoría de categorías, el funtor contravariante . Obedece esencialmente las mismas leyes que los functors (preserva (co) composición e identidad). En realidad, un funtor contravariante es exactamente un funtor de la categoría opuesta. Ya que estamos interesados ​​en los "funtores haskell" que se supone que son endo-functores, podemos ver que un "functor contravariante haskell" es un functor Hask -> Hask_Op .

Por otro lado, ¿qué pasa con

a -> f (f a)

¿Qué leyes debería tener esto? Tengo una sugerencia. En la teoría de categorías, es posible mapear entre Functors. Dados dos funtores de F, G cada uno de categoría C a categoría D , una transformación natural de F a G es un morfismo en D

forall a. F a -> G a

Eso obedece a ciertas leyes de coherencia. Puede hacer muchas cosas con transformaciones naturales, incluso usarlas para definir una "categoría de functor". Pero, el chiste clásico (debido a Mac Lane) es que las categorías se inventaron para hablar sobre los funtores, los funtores se inventaron para hablar sobre las transformaciones naturales y las transformaciones naturales para hablar sobre las adyuvantes .

Un functor F : D -> C y un functor G : C -> D forman una unión de C a D si existen dos transformaciones naturales

unit : Id -> G . F
counit : F . G -> Id

Esta idea de un complemento es una forma frecuente de entender las mónadas. Cada adyuvancia da lugar a una mónada de una manera totalmente natural. Es decir, dado que la composición de estos dos functores es un endofunctor, y usted tiene algo parecido a la devolución (la unidad), todo lo que necesita es la unión. Pero eso es fácil, unirse es solo una función G . F . G . F -> G . F G . F . G . F -> G . F G . F . G . F -> G . F que se obtiene simplemente usando el counit "en el medio".

Entonces, con todo esto, ¿qué es lo que estás buscando? Bien

dneg :: a -> n (n a)

Se ve exactamente como la unit de la unión de un funtor contravariante consigo mismo. Por lo tanto, su tipo de Nomad es probable (ciertamente si su uso para construir una mónada es correcto) exactamente igual que "un funtor contravariante que es autoadjuntivo". La búsqueda de los funtores adjuntos lo llevará de nuevo a la doble negación y al paso de Continuación ... ¡que es justo donde empezamos!

EDITAR: Es casi seguro que algunas de las flechas de arriba están hacia atrás. Sin embargo, la idea básica es correcta. Puedes hacerlo tú mismo usando las citas a continuación:

Los mejores libros sobre teoría de categorías son, probablemente,

• Steve Awodey, Categoría Teoría
• Sanders Mac Lane, categorías para el matemático que trabaja

aunque existen numerosos libros de introducción más accesibles, incluido el libro de Benjamin Pierces sobre la teoría de la categoría para científicos informáticos.

Video conferencias online.

• La clase de conferencias teóricas de Steve Awodey de la Escuela de Verano del Lenguaje de Programación de Oregon
• Las breves conferencias de Catsters en youtube, indexadas aquí , prestan especial atención a los videos adjuntos.

Varios documentos exploran el ángulo de unión en la mónada de continuación, por ejemplo

• Hayo Thielecke, Semántica de Continuación y Autoadjunto

Los términos de búsqueda "auto adjunto", "continuación" y "mónada" son buenos. Además, varios bloggers han escrito sobre estos temas. Si busca en Google "de dónde vienen las mónadas", obtendrá resultados útiles como este de la categoría n cafe, o este de sigfpe. También el link Sjoerd Vissche al lector Comonad.