jeudi 10 juin 2010

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 !

Aucun commentaire: