haskell - category theory for programmers

¿Cómo es un comonoide no trivial?

Question

Los comonoides se mencionan, por ejemplo, en los documentos de la biblioteca distributive de Haskell:

Debido a la falta de comonoides no triviales en Haskell, podemos restringirnos a requerir un Functor en lugar de alguna clase Coapplicativa.

Después de una pequeña búsqueda, encontré una respuesta de StackOverflow que explica esto un poco más con las leyes que los comonoides tendrían que cumplir. Así que creo que entiendo por qué solo hay una posible instancia para una hipotética clase de tipos Comonoid en Haskell.

Por lo tanto, para encontrar un comonoide no trivial, supongo que tendríamos que buscar en alguna otra categoría. Seguramente, si los teóricos de la categoría tienen un nombre para comonoides, entonces hay algunos interesantes. Las otras respuestas en esa página parecen insinuar un ejemplo que involucra a Supply , pero no pude encontrar una que cumpla con las leyes.

También recurrí a Wikipedia: hay una página para los monoides que no hace referencia a la teoría de categorías, que me parece una descripción adecuada de la clase de tipos Monoides de Haskell, pero el "comonoide" redirige a una descripción de la categoría de teoría de los monoides y comonoides juntos. No puedo entender, y todavía no parece haber ningún ejemplo interesante.

Así que mis preguntas son:

1. ¿Se pueden explicar los comonoides en términos no teóricos de categoría como los monoides?
2. ¿Cuál es un ejemplo simple de un comonoide interesante, incluso si no es un tipo Haskell? (¿Se podría encontrar uno en una categoría de Kleisli sobre una mónada Haskell familiar?)

edición: no estoy seguro si esto es en realidad una categoría teóricamente correcta, pero lo que estaba imaginando en la paréntesis de la pregunta 2 no era una definición trivial de delete :: a -> m () y split :: a -> m (a, a) para algunos tipos específicos de Haskell a y Haskell mónada que satisfacen las versiones de las leyes de comonoides de la flecha de Kleisli en la respuesta vinculada. Otros ejemplos de comonoides son todavía bienvenidos.

Answer 1

1. Un monoide en el sentido habitual es lo mismo que un monoide categórico en la categoría de conjuntos. Uno esperaría que un comonoide en el sentido habitual sea lo mismo que un comonoide categórico en la categoría de conjuntos. Pero cada conjunto en la categoría de conjuntos es un comonoide de manera trivial, por lo que aparentemente no hay una descripción no categórica de comonoides que sea paralela a la de los monoides.
2. Al igual que una mónada es un monoide en la categoría de endofunctores (¿cuál es el problema?), Un comonad es un comonoide en la categoría de endofunctores (¿cuál es el problema?) Entonces, cualquier comuna en Haskell sería un ejemplo de comonoide.

Answer 2

Bueno, una forma en la que podemos pensar que un monoide es enganchado a cualquier construcción de producto en particular que estemos usando, por lo que en Set tomaríamos esta firma:

mul : A * A -> A
one : A

a este:

dup : A -> A * A
one : A

pero la idea de dualidad es que las afirmaciones lógicas que puede hacer que todos tengan duales que se pueden aplicar a los objetos duales, y hay otra forma de indicar qué es un monoide, y eso es ser negativo para la elección de la construcción del producto y luego Cuando tomamos la estructura, podemos tomar el coproducto en la salida, como:

div : A -> A + A
one : A

donde + es una suma etiquetada. Aquí esencialmente tenemos que todos los términos que están en este tipo siempre están listos para producir un nuevo bit, que se deriva implícitamente de la etiqueta utilizada para denotar la instancia izquierda o derecha de A. Personalmente, creo que esto es realmente genial. Creo que la versión genial de las cosas de las que la gente hablaba anteriormente es cuando no construyes particularmente eso para los monoides, sino para las acciones de los monoides.

Se dice que un monoide M actúa sobre un conjunto A si hay una función

act : M * A -> A

donde tenemos las siguientes reglas

act identity a = a
act f (act g a) = act (f * g) a

Si queremos una coacción, ¿qué queremos exactamente?

act : A -> M * A

¡Esto nos genera un flujo del tipo de nuestro comonoide! Estoy teniendo muchos problemas para crear las leyes de estos sistemas, pero creo que deben estar en algún lugar, así que seguiré buscando esta noche. Si alguien me puede decir o que estoy equivocado acerca de estas cosas de una manera u otra, también estoy interesado en eso.

Answer 3

Como mencionó Phillip JF, es interesante hablar de comonoides en lógicas subestructurales. Hablemos del cálculo lambda lineal. Esto es muy parecido a su cálculo lambda tipificado normal, excepto que cada variable debe usarse exactamente una vez.

Para tener una idea, contemos las funciones lineales de los tipos dados , es decir,

a -> a

tiene exactamente un habitante, id . Mientras

(a,a) -> (a,a)

Tiene dos, id y flip . Tenga en cuenta que en el cálculo lambda regular (a,a) -> (a,a) tiene cuatro habitantes

(a, b) ↦ (a, a)
(a, b) ↦ (b, b)
(a, b) ↦ (a, b)
(a, b) ↦ (b, a)

pero los dos primeros requieren que usemos uno de los argumentos dos veces mientras descartamos el otro. Esta es exactamente la esencia del cálculo lambda lineal: no permitir ese tipo de funciones.

Dejando de lado rápidamente, ¿cuál es el punto de LC lineal? Bueno, podemos usarlo para modelar efectos lineales o uso de recursos. Si, por ejemplo, tenemos un tipo de archivo y algunos transformadores, puede que parezca

data File
open  :: String -> File
close :: File   -> ()      -- consumes a file, but we''re ignoring purity right now
t1    :: File -> File
t2    :: File -> File

y luego las siguientes son tuberías válidas:

close . t1 . t2 . open
close . t2 . t1 . open
close . t1      . open
close . t2      . open

pero este cálculo de "ramificación" no es

let f1 = open "foo"
    f2 = t1 f1
    f3 = t2 f1
in close f3

ya que usamos f1 dos veces.

Ahora, es posible que se esté preguntando algo en este punto acerca de qué cosas deben seguir las reglas lineales. Por ejemplo, decidí que algunas tuberías no tienen que incluir t1 y t2 (compare el ejercicio de enumeración anterior). Además, introduje las funciones de open y close que crean y destruyen felizmente el tipo de File pesar de ser una violación de la linealidad.

De hecho, podríamos postular la existencia de funciones que violan la linealidad, pero no todos los clientes pueden hacerlo. Se parece mucho a la mónada IO : todos los secretos se encuentran dentro de la implementación de IO para que los usuarios trabajen en un mundo "puro".

Y aquí es donde entra Comonoid .

class Comonoid m where
  destroy :: m -> ()
  split   :: m -> (m, m)

Un tipo que Comonoid una instancia de Comonoid en un cálculo lambda lineal es un tipo que tiene reglas de destrucción y duplicación. En otras palabras, es un tipo que no está del todo limitado por el cálculo lambda lineal.

Ya que Haskell no implementa las reglas de cálculo lambda lineal en absoluto, siempre podemos instanciar Comonoid

instance Comonoid a where
  destroy a = ()
  split a   = (a, a)

O, tal vez, la otra forma de verlo es que Haskell es un sistema LC lineal que simplemente Comonoid instancia de Comonoid para cada tipo y aplica destroy y split automáticamente.