Monoïdes, Flèches, et Pliables: un cas particulier

Voici un joli exemple de la puissance du polymorphisme en Haskell. Le contexte est similaire au problème dit de "stream fusion": il s'agit d'effectuer en une seule passe plusieurs calculs qui demandent d'itérer sur une structure de données. L'exemple classique consiste à calculer la moyenne d'une liste:

average xs = sum xs / length xs

Cette expression est inefficace, parce que le programme va traverser la liste deux fois: une fois pour calculer le sum, une fois pour le length. Bien sur, on peut éviter le double passage en implémentant la récursion à la main:

average = uncurry (/) . foldAverage (0,0) where
    foldAverage (sum,length) [] = (sum,length)
    foldAverage (sum,length) (x:xs) = foldAverage (sum+x,length+1) xs

Ce qui a le désavantage d'être plutôt moche; exprimons le plutôt avec un fold:

average = uncurry (/) . foldl' (\(s,l) x -> (s+x,l+1)) (0,0)

Mieux, sans être extraordinaire. Observons qu'encore une fois, les deux opérations qui nous intéressent (la longeur et la somme) son associatives et admettent un neutre: nous sommes donc en présence d'un Monoid.

Coup de chance, ces deux notions qui nous intéressent sont déja dans la lib standard sous la forme du wrapper Sum, qui transfome n'importe quel Num en Monoid sous l'addition. Mieux: il existe une instance

(Monoid a, Monoid b) => Monoid (a,b)

Qui fait ce que vous pensez: appliquer deux mappend ou mconcat en parallèle.

Pour calculer notre moyenne, commençons par mapper chaque élément de la liste vers une paire de Monoids additifs, effectuons le concat, et il restera la division finale:

average = (\(s,l) -> getSum s / getSum l) . mconcat . map (\x -> (Sum x, Sum 1))

Encore un peu trop verbeux à mon goût: les lambdas peuvent être éliminés grâce aux combinateurs de flèches:

import Control.Arrow
average = uncurry (/) . (getSum *** getSum)
        . mconcat . map (Sum &&& (Sum.const 1))

Cette fois-ci, nous sommes PointFree, un progrès apréciable. Mais nous pouvons encore améliorer les choses. Par exemple, et si nous généralisions la fonction à d'autres types de données (arbres, arrays, ...)

Nous avons utilisé mconcat, qui n'est autre qu'un fold de mappend. Si nous disposons d'un fold générique pour une structure de données, nous pouvons généraliser. Il existe une classe à ce dessein, la classe Foldable. La définition minimale d'un type Foldable consiste en une seule fonction:

instance Foldable t where
    foldMap :: (Monoid m) => (a  -> m) -> t a -> m

Qui applique une fonction (a->m) au contenu de la structure pour obtenir un Monoid, sur lequel on appelle mappend. Passer par un Monoid garantit que l'opération est associative, ce qui permet dans certains cas d'explorer la structure très efficacement (sujet d'un prochain article).

Evidemment, par défaut les Lists sont Foldable, et nous pouvons donc réécrire average en utilisant Foldable:

average = uncurry (/) . (getSum *** getSum) . foldMap (Sum &&& (Sum.const 1)

Pour la petite histoire: Il existe deux wrappers Bool, les Monoids And et Or, qui utilisent respectivement (&&) et (||) comme opération. Ceci permet d'écrire très simplement une fonction pour controler en une passe si un ensemble de Booléens ne contient que des True, que des False, ou un mix des deux:

alltruefalse = (getAny *** getAll) . foldMap (Any &&& All)

Cette expression est équivalente à  (or &&& and), avec l'avantage de calculer les deux folds en une seule passe....

   ... ou pas. Cette fonction est en réalité complètement stupide pour deux raisons:

1. La définition du Monoid sur les tuples est trop stricte, et force l'itération de la liste jusqu'a la fin, même en présence de deux folds paresseux et court-circuités. Ce qui nous amène au point suivant,
2. or et and sont court-circuités par défaut, et au moins un de ces deux terminera son évaluation immédiatement après le 1er élément (Si le premier élément est True, or retourne True, sinon and retourne False). La fusion des folds n'a donc aucun intérêt dans ce cas particulier !

Haskell, c'est concis !

Considérez le problème de la rotation d'une liste: On dispose d'une liste xs de longueur inconnue, on souhaite effectuer une rotation de n positions (déplacer n éléments du début à la fin.) Faisons une tentative d'implémentation en Haskell, tout a fait normale, en utilisant la récursion sur n:

rotate 0 xs = xs 

rotate n (x:xs) = rotate (n-1) (xs ++ [x])

C'est bien connu, le ++[x] est très loin d'être efficace (Les listes sont simplement chainées, et immutables, ce qui implique une réallocation complète de l'argument à gauche, donc ici O(l*n) allocations).

Sacrifions un peu de généralité pour une meilleure implémentation (mais qui n'accepte pas de n supérieur à la taille de la liste):

rotate n xs = (drop n xs) ++ (take n xs)

take est une fonction de la librairie standard qui retourne les n premiers éléments d'une liste, tandis que drop retire ces mêmes n premiers éléments.

Concis ? pas encore assez. Intéressons-nous à une classe souvent sous-estimée, le Monoid, dont voici la définition:

class Monoid m where

    mzero :: m

    mappend :: m -> m -> m

    mconcat :: [m] -> m

    mconcat = foldr mappend mzero

Rien d'extraordinaire ici, la classe Monoid regroupe les types pour lesquels il existe une opération naturelle associative, mappend, et un élément neutre des deux côtés, mzero.  Quant à mconcat, c'est une fonction de convenance dont la définition par défaut est donnée.

Il existe beaucoup d'exemples de Monoids; on peut citer les nombres entiers dans deux contextes différents (addition et multiplication), le type Ordering (pour décrire un ordre hiérarchique), mais plus simplement: les listes !

Dans le cas des listes, on à simplement

instance Monoid [a] where

    mzero = []

    mappend = (++)

    mconcat = concat

Comme les Monoids sont fort utiles, on peut généraliser le sens de (++) et de concat à tous les Monoids (c'est d'ailleurs le cas en Caleskell):

import Prelude hiding ((++), concat)

import Data.Monoid

(++) = mappend

concat = mconcat

Ceci nous permet donc d'utiliser (++) sur n'importe quel Monoid, et pas seulement sur les listes.


Voyez-vous ou tout ceci nous mène ? Probablement pas encore, sauf si vous
connaissez l'existence de l'instance suivante (dans la librairie standard):

instance Monoid a => Monoid (t -> a)

 
dont l'implémentation est laissée comme un exercice au lecteur ;)

Traduction: si les listes [a] forment un Monoid, les fonctions (t -> [a]) en forment également un ! ce qui me permet par exemple de remplacer la définition

f x = g x ++ h x

par une plus concise:

f = g ++ h

A condition que x soit d'un type appartenant à la classe Monoid.

Encore plus fort, notre instance est récursive ! en effet, on à

instance Monoid b => Monoid (t' -> b)

(on a juste renommé les variables de type).

Posons b = (t -> a),  on a alors Monoid a => Monoid b, qui se dérive en

instance Monoid a => Monoid (t' -> (t -> a))

C'est exact, le truc fonctionne également sur les fonctions à plus d'un argument ! Ce qui nous permet de simplifier immédiatement

rotate n xs = (drop n xs) ++ (take n xs)

en

rotate = drop ++ take

Si ça c'est pas de la concision...