Simplicité fonctionnelle


Le projet Euler

Le projet Euler est un site présentant des challenges de nature mathématiques mais résolvables sans être mathématicien. Le but est ici de programmer une solution élégante et efficace à ces problèmes dont l'énoncé est souvent simple tout en pouvant présenter des difficultés techniques : une solution en C ou Java pourrait avoir des difficultés avec les overflows d'entiers, par exemple. Attention, ce post comporte les solutions de 3 problèmes.

J'essaye de résoudre ces problèmes en Haskell et les solutions sont souvent très élégantes (je trouve :). Mais paradoxalement, discuter de ces solutions sur IRC ou en IM a amené à des débats sur la lisibilité de mon code, les réactions étant le plus souvent "o_O omgwtflol". La difficulté vient sans doute des paradigmes utilisés en Haskell, qui sont bien différents de ce qui se fait dans des langages impératifs. L'un de ces paradigmes est l'application partielle de fonction, un autre la composition de fonction.

Application partielle

En C, C++, Java, une fonction a un nombre de paramètres, et doit être appelée avec ce nombre de paramètres uniquement (laissons de côté les va_args). Créer une fonction qui prend un nombre variable d'arguments et renvoie soit une fonction soit un nombre n'est ainsi pas une tâche triviale. Pourquoi faire cela ? Pour pouvoir passer des fonction même lorsque l'on ne connaît pas tous les paramètres. Si je veux créer une fonction d'augmentation de salaire pour une liste d'empolyés, je vais d'abord créer une fonction augmenter (qui prend un employé et renvoie un nouvel employé avec le salaire mis à jour). Je peux appliquer cette fonction à un seul employé, et non pas à tout un groupe. Pour appliquer une fonction à un groupe, je vais utiliser map : map(f, l) applique la fonction f à chacun des éléments et renvoie la liste des résultats. On peut donc écrire :

augmenterGroupe = map augmenter

map prend deux paramètres (la fonction et la liste) pour donner une liste. Cela signifie qu'il manque une liste à augmenterGroupe pour obtenir une liste d'employés augmentés. Mais je peux maintenant écrire :

augmenterGroupe cadres
augmenterGroupe ouvriers
augmenterGroupe stagiaires

pour augmenter tout le monde du même pourcentage. Enfin un exemple réaliste ! Cette application partielle me permet donc d'utiliser des fonctions de n paramètres en leur ayant passé m < n paramètres pour obtenir ainsi une fonction des n - m paramètres restants.

Il n'est pas toujours facile de lire un code comprenant des fonctions dont la liste de paramètres n'est pas terminée, mais cela donne un avantage certain dans l'écriture de combinaisons de fonctions.

Composition de fonctions

En mathématiques, il est possible de créer une fonction étant la combinaison de deux autres : on écrit cela (f o g)(x), ce qui est identique à f(g(x)). (f o g o h o i o j)(x) est quand même plus lisible que f(g(h(i(j(x)))), non ? Aviez-vous remarqué qu'il manquait une parenthèse fermante, d'ailleurs ? Haskell fournit l'opérateur point (.) qui permet de combiner deux fonctions ensemble.

Lorsque l'on combine plusieurs fonctions avec des ronds, on crée une nouvelle fonction dont on ne spécifie pas les points d'applications (le x dans f(x)=...). L'utilisation de rond et de l'application partielle amène au style "point-free". Pas parce qu'il ne contient pas beaucoup de caractères points, mais parce qu'il ne contient pas beaucoup de noms de variables. Ainsi, écrire f x = x + 1 peut se simplifier en f = (1+). Pourquoi avoir à spécifier le point x d'application de la fonction lorsqu'il est évident ?

Ce post de comp.lang.functional fait le parallèle avec l'enchaînement de commandes dans un shell :

Sample Unix shell command:

  grep '^X-Spam-Level' | sort | unique | wc -l

Sample Haskell function:

  length . nub . sort . filter (isPrefixOf "X-Spam-Level")

Cela dit, l'exemple est bien choisi. Il est souvent possible de rendre une fonction incompréhensible en en enlevant les noms des points d'application et en utilisant des points à la place.Par exemple :

instead of:

  foo x y = 2 * x + y

one has, in point-free style:

  foo = (+) . (2 *)

[...]

numOccurrences x = length . filter (== x)

Once you see this, it's easy to go back to a fully pointful version:
numOccurrences x y = length (filter (== x) y)

Or you can go the other way, to a point-free version:

numOccurrences = (length .) . filter . (==)
which I find confusing.

Bien d'accord avec cet exemple. La notation sans aucun point est parfois difficile à lire et vaut au style point-free le surnom de "point-less".Il existe des mécanismes de suppression de points dans un code Haskell. Lambdabot dispose d'une commande @pl, qui donne parfois des résultats surprenants :

12:28:23    <tonfa>    if you have a list with an infinite number of increasing value, how do you get the sum of all the value less than a given number ?
[...]
12:30:06    <MyCatVerbs>    > (\y z-> takeWhile (\x-> x<y) z) 15 [1..]
12:30:07    <lambdabot>    [1,2,3,4,5,6,7,8,9,10,11,12,13,14]
12:30:12    <MyCatVerbs>    Ah, sehr gut.
12:30:20    <vincenz>    @pl (\y z-> takeWhile (\x-> x<y) z)
12:30:21    <lambdabot>    takeWhile . flip (<)
12:30:33    <MyCatVerbs>    ...whaaaat.

Sa fonction du départ était à peu près lisible (y la limite et z la liste, la fonction de test utilisant x comme valeur comparée à la limite y), et lambdabot l'a transformée en "takeWhile . flip (<)", qui est difficilement compréhensible au premier abord. À noter tout de même que peu de langages permettent de manipuler des listes infinies :)

Revenons-en au projet Euler...

Voici des solutions faciles et décomposées à quelques exercices du projet Euler:-- #16: What is the sum of the digits of the number 21000?
*Euler> 2 ^ 1000
10715086071862673209...   -- un grand nombre
*Euler> show $ 2 ^ 1000
"10715086071862673209...   -- une chaîne maintenant
*Euler> map Char.digitToInt . show $ 2 ^ 1000
[1,0,7,1,5,0,8,6,0,7,1,8,6,2,6,7,3,2,0,9... -- une liste de nombres...
*Euler> sum . map Char.digitToInt . show $ 2 ^ 1000
1366   -- dont on prend la somme.


-- #25: What is the first term in the Fibonacci sequence
-- to contain 1000 digits?

*Euler> let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
-- la liste infinie des nombres de Fibonacci
*Euler> :t (fibs !!)     
(fibs !!) :: Int -> Integer  
-- la fonction qui prend x et renvoie fibs[x]
*Euler> :t (length . show . (fibs !!))
(length . show . (fibs !!)) :: Int -> Int  
-- la fonction qui prend x et renvoie la taille de fibs[x]
*Euler> :t ((1000 >) . length . show . (fibs !!))
((1000 >) . length . show . (fibs !!)) :: Int -> Bool 
-- la fonction qui prend x et renvoie True si fibs[x] a moins de 1000 chiffres

f25 = head $ dropWhile ((1000 >) . length . show . (fibs !!)) [0..] where
    fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
-- en partant de fibs[0] jusqu'à l'infini, laisser tomber
-- tous les nombres de Fibonacci dont la taille est de moins
-- de 1000 chiffres. En fait, garder juste le premier (head).


-- Dans le même genre que la 16 :
-- #48: Find the last ten digits of 11 + 22 + ... + 10001000.

*Euler> map (\i -> i^i) [1..1000]
-- ici, la liste de tous les i^i pour i allant de 1 à 1000 inclus.
*Euler> sum $ map (\i -> i^i) [1..1000]
10003681991446951770... -- la somme de l'ensemble du dessus
*Euler> show . sum $ map (\i -> i^i) [1..1000]
"10003681991446951770...     -- pareil, mais en chaîne.
-- on veut les dix derniers nombres, il suffit donc de retourner
-- la chaîne, prendre les 10 premiers, et les retourner encore.
*Euler> reverse . show . sum $ map (\i -> i^i) [1..1000]
"00764801191872187976... -- comme au dessus, mais retourné.
*Euler> take 10 . reverse . show . sum $ map (\i -> i^i) [1..1000]
"0076480119"
-- seulement les 10 derniers nombres de la grande somme, à l'envers.

f48 = reverse . take 10 . reverse . show . sum $ map (\i -> i^i) [1..1000]
"9110846700"

OK, ça se lit de droite à gauche... mais on fait difficilement plus simple ! Alors que j'avance dans mon apprentissage du langage, j'ai moins de moments impressionnants que lors de mes permiers pas avec Haskell, où j'étais sans cesse émerveillé. Cela dit, la lecture il y a quelques semaines d'un papier sur les performances de l'évaluation paresseuse comportait une ligne utilisant Y, qui ne manque pas de me scotcher :

iterate f x = x : iterate f (f x) -- simple, et réécrit en :
iterate f x = fix((x:) . map f) where fix f = y where y = f y

-- à noter qu'on peut l'écrire plus simplement :
iterate f x = y((x:) . map f) where y f = f (y f)

La combinaison n'est certes pas simple, mais cette récursion est... Mind-blowing. Je ne sais pas vraiment comment l'exprimer, mais cette photo devrait faire l'affaire :


Ce post est un peu plus long que ce que j'avais prévu... j'espère quand même que le message principal est passé : des langages différents ont des paradigmes nouveaux et parfois difficiles à aborder. Cela ne veut pas dire qu'ils sont complexes. Le projet Euler fournit de bons exemples de problèmes triviaux pour des développeurs Haskell, et qui peuvent pourtant mettre en difficulté les développeurs Java, C++.