foldl est un fold, tu le trouveras sous le nom de fold_left, reduce, inject... selon les langages, sa définition sur les listes est simple :
1 2
| foldl f y [] = y
foldl f y (x:xs) = foldl f (f y x) xs |
Prenons un exemple simple :
1 2 3 4 5
| foldl (+) 0 [1,2,3]
== foldl (+) (0 + 1) [2,3]
== foldl (+) ((0+1) + 2) [3]
== foldl (+) (((0+1) + 2) + 3) []
== ((0+1) + 2) + 3 |
Avec une fonction quelconque :
foldl f 0 [1,2,3] == f (f (f 0 1) 2) 3
Dans les langages stricts, foldl est souvent apprécié parce qu'il est terminalement récursif, autrement dit il est possible d'optimiser le code généré pour que foldl n'accumule pas ses appels récursifs dans la pile. En Haskell la situation est plus ambigüe parce que bien que foldl en lui-même ne puisse pas provoquer de dépassement de pile, il peut créer des thunks (des bouts de code en attente d'évaluation) qui eux provoque un tel débordement. "foldl (+) 0" est lui-même sujet à ce problème. C'est pourquoi il est extrêmement rare de voir foldl dans un programme réel en Haskell, tu trouveras plutôt foldr ou foldl' à la place. Je te renvoie à cette page du wiki pour une explication plus en profondeur.
Les backquotes ` sont utilisés pour transformer une fonction normale en opérateur infixe, tout comme les parenthèses () sont utilisés pour transformer un opérateur infixe en fonction normale :
1 2
| préfixe : (+), f
infixe : +, `f` |
Il y a un certain nombre de fonctions en Haskell qui sont plutôt prévues pour être utilisées en infixe : elem ou mplus par exemple.
1 2
| 5 `elem` [1..10], (5 `elem`), (`elem` "+*-/")
Nothing `mplus` Just 5 |
Enfin (.) : c'est un opérateur infixe, au même titre que (+) ou (*), il s'agit de la composition de fonctions. En Mathématiques tu as sûrement vu que si tu avais deux fonctions f et g, tu pouvais les combiner f•g (souvent lu "f rond g" ou "f après g") de sorte que (f•g)(x) soit équivalent à f(g(x)). (.) est l'opérateur Haskell qui fait ça, sa définition est simplement :
Haskell est très bien adapté au style dit "pointfree" ("libre du point" "sans points", le "point" ici désignant les arguments explicite, comme x dans la définition "f x = x + 5") et l'opérateur (.) est un élément essentiel pour ce style combiné avec les fonctions d'ordre supérieur.
Par exemple cette fonction vérifie que tous les mots d'une chaîne de caractère sont capitalisés (leur première lettre est majuscule) :
capitalisedSentence = all (isUpper . head) . words
Ca se lit de droite à gauche : on découpe en mots (words), puis on vérifie que pour tous les mots (all) leur première lettre (head) est une majuscule (isUpper)
Ce style est considéré élégant et permet souvent d'exprimer avec concision et clarté des idées fort complexe. Il est néanmoins possible d'aller trop loin, d'où la blague qui consiste à appeler ce style "pointless" (qui pourrait se traduit par "sans point" mais signifie "inutile" en anglais), c'est une question d'équilibre.
--
Jedaï
Partager