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...