2010-07-17 16 views
29

Estoy un poco confundido y necesito que alguien me aclare. Vamos a esbozar mi comprensión actual:¿Todos los funtores de Haskell son endofunctores?

Dónde E es un endofunctor y A es alguna categoría:

E : A -> A. 

Desde todos los tipos y morfismos en Haskell están en la categoría Hask, no es ninguna funtor en Haskell también un endofunctor? F : Hask -> Hask.

Tengo un buen presentimiento de que estoy equivocado, y simplifico esto de alguna manera, y me gustaría que alguien me diga qué idiota soy. Gracias.

+0

¿Falta alguna palabra antes de "Where' E' ..."? – kennytm

Respuesta

33

Es posible que desee aclarar si está preguntando acerca de "functors in Haskell", o Functor s. No siempre está claro qué categoría se asume cuando se usan términos de Teoría de categorías en Haskell.

Pero sí, la suposición predeterminada es Hask, que se toma como la categoría de tipos Haskell con funciones como morfismos. En ese caso, un endofunctor F en Hask asignaría cualquier tipo A a un tipo F (A) y cualquier función f entre dos tipos A y B a una función F (f) entre algunos tipos F (A) y F (B).

Si entonces nos limitamos sólo a aquellos endofunctors el que se asignan cualquier tipo a a un tipo (f a) donde f es un constructor de tipos con clase * -> *, entonces podemos describir el mapa asociado para funciones como una función de orden superior con el tipo (a -> b) -> (f a -> f b) , que es, por supuesto, la clase de tipo llamada Functor.

Sin embargo, uno puede imaginar fácilmente endofunctors buen comportamiento en Hask que no puede ser escrito (directamente) como una instancia de Functor, tal como un funtor la asignación de un tipo a a Either a t. Y si bien no hay obviamente mucho sentido en un funtor de Hask a alguna otra categoría totalmente, es razonable considerar un functor (contravariant) de Hask a Haskop.

Más allá de eso, los casos de Functor mapas necesariamente de toda la categoría Hask en algún subconjunto de la misma que, por lo tanto, también forma una categoría. Pero también es razonable hablar de functors entre subconjuntos de Hask. Por ejemplo, considere un funtor que envíe tipos Maybe a a [a].

Es posible que desee leer la category-extras package, que ofrece algunas Categoría Teoría de inspiración estructuras incrustadas dentro Hask en lugar de asumir la totalidad de la misma.

+7

Esto es un poco tangente, pero quería verificar mi comprensión: se puede pensar en un mapeo de Maybe a a [a] de varias maneras: (a) Un functor, donde Maybe y [] forman sub -categorías de Hask. (b) Una transformación natural, donde Maybe y [] forman endofunctors en Hask. (c) Una familia de morfismos en la categoría Hask, de Maybe a a [a] forall a en Obj (Hask). ¿Eso es todo correcto? –

+0

Addendum: (a) y (b) son, por supuesto, contingentes en el mapeo que satisfaga las leyes de los funtores y las transformaciones naturales, respectivamente. ¿Es justo decir que si las leyes de functor se satisfacen para (a), entonces el mismo mapeo se puede ver como (b), y viceversa? –

+0

@Tom: yo ... ¿creo? Me parece correcto. De hecho, creo que cualquier función con el tipo 'forall a. Tal vez a -> [a] * * debe * ser una transformación natural. 'maybeToList' en Data.Maybe, por ejemplo, es (o describe suficientemente) todo lo que usted mencionó, creo, pero mi propia comprensión de la teoría de categorías es bastante limitada, así que no lo tome como un evangelio ... –

7

Un posiblemente relevante (o al menos interesante) discusión con respecto específicamente mónadas se encuentran en el documento "mónadas no tienen que ser endofunctors":

http://www.cs.nott.ac.uk/~txa/publ/Relative_Monads.pdf

+2

Por lo que vale, las mónadas en el sentido de Categoría de Teoría estándar se definen como endofunctors, mientras que la clase de tipo 'Monad' es un concepto más estrecho, tanto de la misma manera que describo para' Functor' como con algunas complicaciones adicionales resultantes de la muy invasiva estructura cartesiana cerrada de ** Hask **. –

13

Incluso si en última instancia, manipular Hask, hay una muchas otras categorías que se pueden construir en Hask, que puede ser significativo para el problema en cuestión:

  • Hask^op, que es Hask con todas las flechas invertidas
  • Hask * Hask, funtores en él son bifunctors
  • categorías coma, es decir. los objetos son morfismos a un objeto fijo a, morfismos son triángulos conmutativa
  • categorías Functor, morfismos son transformaciones naturales Categorías
  • Álgebra
  • categorías
  • monoidales
  • Categorías
  • Kleisli
  • ...

tome una copia de Mac Lane's Categorías para el matemático de trabajo para tener definiciones, e intenta encontrar por ti mismo el problema que resuelven en Haskell. Especialmente obstruir los funtores adjuntos (que son objetos iniciales/terminales en la categoría correcta) y su relación con las mónadas.

Vas a ver que incluso si hay una gran categoría (Hask, o "objetos levantados desde Hask con las flechas derecha/productos/...", tal vez, que encapsula las opciones de idioma de Haskell como no rigurosidad y pereza), las categorías derivadas apropiadas son expresivas.

+0

Muchas gracias. Puedo ver ese libro. –

+9

Ten en cuenta que debes leer este libro con un _purpose_ (ya sea programación funcional o geometría algebraica, o lo que sea), porque es bastante escueto en cuanto a los ejemplos, y de alguna manera debes proporcionar _yours_. Sin embargo, eso lo convierte en un libro increíblemente flexible, utilizado por científicos de horizontes muy diversos. –

Cuestiones relacionadas