Les catégories

La théorie des catégories, créée dans les années 1940, a progressivement remplacé la théorie des ensembles comme outil de base pour exprimer les structures mathématiques. Dans les ensembles, on travaille avec les éléments ; dans les catégories, on travaille avec les flèches, qui expriment une relation entre 2 objets.
Le définition d'une catégorie est très simple, mais travailler avec des catégories oblige à changer notre manière habituelle de penser (utiliser les flèches au lieu des éléments). La théorie des catégories contient de nombreuses notions : construction universelle, foncteurs, transformations naturelles.

Historique

Les catégories ont été créées par deux mathématiciens américains, Saunders Mac Lane et Samuel Eilenberg. Les catégories ont intégré l'informatique théorique en 1980. On avait déjà l'isomorphisme de Curry-Howard, qui assimile un type informatique à une proposition logique - et le passage d'un type à l'autre (une fonction pure) à une démonstration. Lambek a montré qu'un type (ou une proposition logique) peut aussi être assimilé à un objet d'une "catégorie cartésienne fermée" - et les fonctions (ou preuves) aux flèches de cette catégorie. On parle de la correspondance (ou isomorphisme) de Curry-Howard-Lambek.

Définition

Dans une catégorie, on a des objets et des flèches qui vont d'un objet à l'autre. Une flèche exprime une relation entre 2 objets.

Une catégorie est donc un graphe orienté : les objets sont les sommets et les flèches sont les arêtes.
Mais pour qu'un graphe orienté mérite le nom de catégorie, les flèches doivent vérifier certaines propriétés :
  1. Identité : Tout objet doit avoir une flèche qui part de cet objet et arrive à cet objet sans rien changer.
    On note idA l'indentité de l'objet A.
  2. Composition : s'il existe une flèche de A vers B et une flèche de B vers C, alors il doit exister une flèche qui va directement de A à C.
    Aller de A à B puis de B à C revient exactement au même que d'aller directement de A à C. Composition dans une catégorie La flèche qui va directement de A à C s'appelle la composée de f et de g.
    On note g ( f ) = g ∘ f
    g∘f se prononce " g rond f ". Cette notation n'est pas intuitive car elle est à l'envers, mais elle est logique, car on applique g au résultat de f.
    A la place de " g rond f ", on pourrait dire " g de f ".
  3. Associativité : le chemin parcouru ne change pas le résultat. Associativité dans une catégorie h ∘ (g ∘ f) = (h ∘ g) ∘ f
    La flèche qui va directement de A à D peut donc s'écrire h ∘ g ∘ f, sans les parenthèses.
Et c'est tout.

Le fait d'avoir des flèches en plus des objets permet de représenter de nombreux phénomènes de manière naturelle.
Dans la théorie des ensembles, on travaille avc les éléments.
Dans la théorie des catégories, on travaille avec les flèches.
Pour une illustration de cette différence, voir les fonctions

Catégorie des ensembles

La catégorie la plus familière à étudier est la catégorie des ensembles, notée Set ou Ens, qui contient tous les ensembles possibles.
Dans cette catégorie,
- un objet est un ensemble,
- une flèche est une relation entre 2 ensembles.
Noter que dans cette catégorie, n'importe quel ensemble est représenté par un objet. On sait avec quels ensembles on travaille, on connaît leur structure interne, mais quand on travaille dans une catégorie, un objet est comme un point, sans structure, on n'a pas de moyen d'utiliser les propriétés internes des objets. On utilise à la place les propriétés des flèches et de leur composition.

Catégorie des types et des fonctions

Cette catégorie permet de modéliser un langage informatique comprenant :

Types de données

Un type de donnée peut être représenté par un ensemble dont les éléments sont les valeurs que peut prendre ce type.

Ce sont des ensembles finis ou infinis :
TypeEnsembleN : cardinal de l'ensemble
Boolean true, false 2
Char 'a', 'b', ... 128
Integer 1, 2, 3 ... infini
Real 0.0001, 0.0002 ... infini
String "", "a", "aa" ... infini
Certains types ont en théorie un nombre inifni de valeurs mais en pratique un nombre fini car limité par les capacités de la machine.

Fonctions pures

Une fonction au sens mathématique du terme : f(x) = y, prend en entrée un paramètre et renvoie une valeur.
La définition d'une fonction pure est moins stricte ; une fonction est dite pure si : Par exemple :
// char --> boolean
boolean isVoyelle(char c){ }
En pratique, les fonctions diffèrent des fonctions mathématiques car elles peuvent : Mais toutes ces complexités peuvent être construites à partir de fonctions pures à un seul paramètre, ce qui permet de définir une catégorie des types comme un cas particulier de Set car un type peut être représenté par un ensemble.

La catégorie des types fournit donc une représentation mathématique d'un langage fonctionnel.

Quelques liens