Pourquoi les foncteurs Haskell ont-ils uniquement des types dérivés dans leur catégorie cible?

Dans Haskell, le foncteur de classe de types Functor est défini comme suit (voir par exemple le wiki Haskell ):

class Functor (f :: * -> *) where
  fmap :: (a -> b) -> f a -> f b 

Pour autant que je comprends (s'il vous plaît me corriger si je me trompe), un tel foncteur ne peut avoir que la catégorie cible une catégorie construite en utilisant un constructeur de type, par exemple [], Maybeetc. D'autre part, on peut penser à foncteurs ayant une catégorie comme cible d'un foncteur, par exemple la catégorie de tous les types Haskell. Par exemple, Intpourrait être un objet dans la catégorie cible d'un foncteur, pas seulement Maybe Intou [Int].

Quelle est la motivation de cette restriction sur les foncteurs Haskell?

Il n'y a aucune restriction! Lorsque j'ai commencé à apprendre les bases théoriques des catégories pour les constructeurs de types, ce point m'a également troublé. Nous y reviendrons. Mais d'abord, permettez-moi de dissiper une certaine confusion. Ces deux citations:

un tel foncteur ne peut avoir comme catégorie cible qu'une catégorie construite à l'aide d'un constructeur de type

et

on peut penser à des foncteurs ayant n'importe quelle catégorie comme cible d'un foncteur, par exemple la catégorie de tous les types Haskell

montrez que vous comprenez mal ce qu'est un foncteur (ou, à tout le moins, que vous utilisez mal la terminologie).

Les foncteurs ne construisent pas de catégories. Un foncteur est un mappage entre les catégories. Les foncteurs apportent des objets et des morphismes (types et fonctions) dans la catégorie source à des objets et des morphismes dans la catégorie cible.

Notez que cela signifie qu'un foncteur est en réalité une paire de mappages: un mappage sur les objets F_obj et un mappage sur les morphismes F_morph . Dans Haskell, la partie objet F_obj du foncteur est le nom du constructeur de type (par exemple List), tandis que la partie morphisme est la fonction fmap(c'est au compilateur Haskell de trier ce à quoi fmapnous nous référons dans une expression donnée). Ainsi, nous ne pouvons pas dire que Listc'est un foncteur; seule la combinaison de Listet fmapest un foncteur. Pourtant, les gens abusent de la notation; les programmeurs appellent Listun foncteur, tandis que les théoriciens des catégories utilisent le même symbole pour faire référence aux deux parties du foncteur.

De plus, en programmation, presque tous les foncteurs sont des endofuncteurs , c'est-à-dire que la catégorie source et la cible sont les mêmes - la catégorie de tous les types dans notre langage. Appelons ce type de catégorie . Un endofoncteur F sur Type mappe un type T à un autre type FT et une fonction T -> S à une autre fonction FT -> FS . Cette cartographie doit bien entendu obéir aux lois des foncteurs.

En utilisant Listcomme exemple: nous avons un constructeur de type List : Type -> Type, et une fonction fmap: (a -> b) -> (List a -> List b), qui forment ensemble un foncteur. T

Il y a un dernier point à clarifier. L'écriture List intne crée pas un nouveau type de listes d'entiers. Ce type existait déjà . C'était un objet dans notre catégorie Type . List Intest simplement un moyen de s'y référer.

Maintenant, vous vous demandez pourquoi un foncteur ne peut pas mapper un type sur, disons, Intou String. Mais c'est possible! Il suffit d'utiliser le foncteur d'identité. Pour toute catégorie C , le foncteur identité cartes chaque objet lui - même et morphisme à lui - même. Il est simple de vérifier que ce mappage satisfait aux lois du foncteur. Dans Haskell, ce serait un constructeur de type id : * -> *qui mappe chaque type à lui-même. Par exemple, id intévalue à int.

De plus, on peut même créer des foncteurs constants , qui mappent tous les types à un seul type. Par exemple, le foncteur ToInt : * -> *, où ToInt a = intpour tous les types a, et mappe tous les morphismes à la fonction d'identité entière: fmap f = \x -> x