La conception par les catégories

Source de l’article : le document qui suit est une traduction rigoureuse de l’article de Gabriel Gonzalez paru le 18 août 2012, intitulé The category design pattern. Gabriel est connu pour ses travaux réguliers sur les modèles de compositions, notamment avec sa librairie Haskell Pipes.

La programmation fonctionnelle est de plus en plus populaire, cependant je (ndt: l’auteur s’exprimera souvent à la première personne) veux insister dans cet article sur le fait que la programmation fonctionnelle n’est qu’un aspect d’un paradigme plus large : la programmation composable.

Si vous avez déjà utilisé les Pipes Unix, vous avez pu expérimenter la puissance et la flexibilité de la composition de petits programmes pour créer des nouvelles fonctionnalités. De la même façon, si vous faites de la programmation fonctionnelle, vous savez combien il est aisé de composer un ensemble de petites fonctions simples pour obtenir un programme complet.

La théorie des catégories codifie ce style de composition pour former un modèle de conception (ndt : design pattern) : la catégorie. De plus, la théorie des catégories nous fournit les règles précises à suivre pour créer nos propres abstractions qui respecteront ce modèle de conception : les lois des catégories. Ces lois distinguent le modèle des catégories des autres modèles de conception en fournissant des critères stricts pour qualifier ce qui est composable et ce qui ne l’est pas.

On pourrait facilement croire que ce Saint Graal de la composition n’est qu’un idéal théorique, inapplicable aux problèmes de la programmation quotidienne. En réalité, les principes de la théorie des catégories apparaissent dans de nombreux domaines courants.

Ceci est juste un article parmi de nombreux autres que je compte écrire prochainement, et dans lesquels je m’attacherai à montrer comment appliquer concrètement ce modèle de conception dans vos programmes, y compris dans les plus improbables. Ce premier article va donc s’attacher à présenter les catégories et leur mode de composition.

Les catégories

Je vais proposer une introduction à la théorie des catégories qui s’écarte probablement des présentations courantes. En fait, je vais éviter d’aborder les morphismes, les objets, les domaines et co-domaines afin de me concentrer directement sur la composition, car c’est l’essence du modèle de conception, et donc ce qui concerne avant tout le programmeur.

La théorie des catégories exige que toute catégorie soit munie d’une opération de composition, que nous noterons ○. La première loi impose que l’opération de composition soit associative

(f ○ g) ○ h = f ○ (g  ○ h) = f ○ g ○ h

ce qui est très pratique car cela permet de ne pas se préoccuper des groupements et donc d’éviter les parenthèses.

Cette théorie exige également que l’opération de composition admette un élément neutre, noté id, pour la composition à gauche et à droite.

f ○ id = id ○ f = f

Ces lois forment les lois des catégories.

Remarquez que la définition d’une catégorie n’indique ni comment la composition ○ doit s’opérer, ni la définition de id, ni même la nature de f, g et h. C’est donc à nous de les définir, conformément aux lois.

La puissance du modèle de conception par catégories découle du fait qu’une opération de composition conforme aux lois sera facile à utiliser, intuitive, et dépourvue de cas particulier. C’est la raison pour laquelle nous nous efforcerons de définir nos abstractions selon le modèle des catégories à chaque fois que ce sera possible.

La catégorie des fonctions

Définissons maintenant notre première catégorie, celle des fonctions Haskell !

id  :: (a → a)
id x = x

(○) :: (b → c) → (a → b) → (a → c)
(f ○ g) x = f (g x)

Montrons maintenant que les lois des catégories sont respectées.

-- Identité à gauche : id ○ f = f
id ○ f = λx → id (f x)
       = λx → f x
       = f

-- Identité à droite : f ○ id = f
f ○ id = λx → f (id x)
       = λx → f x
       = f

-- Associativité : (f ○ g) ○ h = f ○ (g ○ h) = f ○ g ○ h
(f ○ g) ○ h = λx → (f ○ g) (h x)
	    = λx → f (g (h x))
	    = λx → f ((g ○ h) x)
	    = λx → (f ○ (g ○ h)) x
	    = f ○ (g ○ h)
            = f ○ g ○ h

La composition des fonctions ordinaires est facile d’utilisation, et pourtant extrêmement puissante, simplement du fait qu’il s’agit d’une catégorie ! Elle nous permet d’exprimer des transformations complexes juste en composant quelques fonctions de base.

bestLangs :: [Language] → [Language]
bestLangs = take 3 ○ sortBy (comparing speed) ○ filter isCool

Hélas, certains programmes ne peuvent être facilement écrits avec des fonctions ordinaires. Devrons-nous dans ce cas renoncer aux catégories ? Eh bien non !

La catégorie de Kleisli

Une autre catégorie couramment rencontrée est celle des fonctions monadiques, qui forment une généralisation des fonctions ordinaires.

Dans les librairies Haskell, l’identité et la compositions pour ces fonctions monadiques sont respectivement notés return et <=<.

return :: (Monad m) => (a → m a)

(<=<)  :: (Monad m) => (b → m c) → (a → m b) → (a → m c)

Les mathématiciens la nomme « catégorie de Kleisli », et les fonctions ci-dessus sont définies dans le module Control.Monad.

Notez que les types de return et <=< sont semblables à ceux de la catégorie des fonctions ordinaires.

id     ::              (a →   a)
return :: (Monad m) => (a → m a)

(○)    ::              (b →   c) → (a →   b) → (a →   c)
(<=<)  :: (Monad m) => (b → m c) → (a → m b) → (a → m c)

Même l’implémentation de <=< ressemble à celle de la composition de fonctions ordinaires.

(f  ○  g) x =             f     (g x)
(f <=< g) x = g x >>= f = f =<< (g x)

Ce n’est pas une coïncidence ! Les fonctions monadiques sont une généralisation des fonctions ordinaires, et la catégorie de Kleisli apporte une composition pour ces fonctions monadiques. Seules les définitions de l’opération de composition et de l’identité changent.

Si cette composition et cette identité forment bien une catégorie, nous devons exiger que les lois suivantes soient respectées.

return <=< f = f                                   -- Identité à gauche

f <=< return = f                                   -- Identité à droite

(f <=< g) <=< h = f <=< (g <=< h) = f <=< g <=< h  -- Associativité

Nous connaissons déjà la définition de <=<

(f <=< g) x = f =<< (g x)

que nous pouvons employer pour développer et vérifier les lois

return <=< f = λx → return =<< (f x) = f x = f

f <=< return = λx → f =<< (return x) = f x = f

(f <=< g) <=< h = λx → (λy → f =<< (g y)) =<< h x
                = λx → f =<< (g =<< (h x))
                = λx → f =<< g =<< (h x)
                = f <=< g <=< h

Si on simplifie un peu, on obtient rapidement

m >>= return = m

return x >>= f = f x

m >>= (λy → g y >>= f) = (m >>= g) >>= f

Cela vous rappelle quelque chose ? Ce sont simplement les lois des monades. Si vous vous demandiez d’où elles proviennent, vous savez maintenant qu’elles découlent simplement des lois des catégories.

Par conséquent, toutes les monades que nous définissons donnent automatiquement naissance à une catégorie. Essayons maintenant de manipuler ces nouvelles catégories.

-- La catégorie de Kleisli pour la monade Maybe
lookup  :: k → [(k, v)] → Maybe v
maximumByMay :: (a → a → Ordering) → [a] → Maybe a

bestSuitor :: [(String, [Suitor])] → Maybe Suitor
bestSuitor = maximumByMay (comparing handsome) <=< lookup "Tall"


-- La catégorie de Kleisli pour la monade liste
children :: Person → [Person]

greatGrandChildren :: Person → [Person]
greatGrandChildren = children <=< children <=< children


-- La catégorie de Kleisli pour la monade IO
spawn      ::  IO a  → IO (IO a)
mapM spawn :: [IO a] → IO [IO a]
sequence   :: [IO a] → IO    [a]

concurrentSequence :: [IO a] → IO [a]
concurrentSequence = sequence <=< mapM spawn

Les monades qui ne respectent pas ces lois sont buggées et contre-intuitives. Si vous ne me croyez pas, demandez aux personnes qui ont utilisé la monade ListT, qui enfreint ces lois.

La catégorie Pipe

Les catégories ne sont pas toujours composées de fonctions. Nous allons utiliser une version basique du type Pipe (du paquet Pipes) comme exemple.

data Pipe a b r  = Pure r
                 | Await (a -> Pipe a b r)
                 | Yield b (Pipe a b r)

Pure    r  <+< _          = Pure r
Yield b p1 <+< p2         = Yield b (p1 <+< p2)
Await   f  <+< Yield b p2 = f b <+< p2
p1         <+< Await   f  = Await $ \a -> p1 <+< f a
_          <+< Pure    r  = Pure r

idP = Await $ \a -> Yield a idP

Vérifions les types déduits par le compilateur:

idP   :: Pipe a a r

(<+<) :: Pipe b c r -> Pipe a b r -> Pipe a c r

Ces types ressemblent à nouveau à ceux de l’identité et de la composition vus ci-dessus. Le lecteur motivé pourra prouver lui-même que nous avons bien affaire à une catégorie.

idP <+< p = p                            -- Identité à gauche

p <+< idP = p                            -- Identité à droite

(p1 <+< p2) <+< p3 = p1 <+< (p2 <+< p3)  -- Associativité

Les Pipes donnent un exemple de comment des fonctionnalités élaborées, qui ne se modélisent pas bien sous forme de fonctions ordinaires, peuvent toutefois être très composables. Je ne vais pas insister sur les possibilités précisent de Pipes, car cette information existe déjà dans le tutoriel.

Si vous vous trouvez face à quelque chose qui n’a pas l’air de se composer correctement, n’abandonnez pas. Il y a de fortes chances qu’une solution de composition existe quand même.

Conclusions

La théorie des catégories se limite à formaliser le principe de composition comme modèle de conception, et laisse ensuite chacun libre de définir ce que fait concrètement la composition. C’est donc à vous de découvrir des nouveaux moyens de composer des choses autres que les fonctions ordinaires. Tant que les lois des catégories sont respectées, tout va bien.

De plus, je suis ravi de constater les applications dans la programmation fonctionnelle (car les fonctions ordinaires forment une catégorie), mais sur le long terme nous devons nous intéresser également à des opérations de composition plus complexes si nous voulons avancer sur des domaines plus compliqués.

Avec un peu de chance, cet article vous aura donné envie d’en savoir plus sur la théorie des catégories. Dans les articles à venir, je développerai les sujets suivants :

• pourquoi les lois des catégories garantissent que le code sera simple, intuitif et dépourvu de cas particulier
• comment les foncteurs permettent de combiner différentes catégories
• comment optimiser du code avec les catégories
• comment utiliser les catégories pour simplifier le raisonnement sur l’égalité entre entités

Accéder à l’article original de Gabriel Gonzalez

La solution de gestion de projet AtikTeam utilise les catégories pour la fiabilité et la rapidité du logiciel