### Le sens de la flèche #### Ce qu'on aimerait bien faire Avec les fonctions anonymes, on peut définir des fonctions comme on définirait des variables : :::haskell mafonction = (\x y -> blabla) -- ce code est équivalent à : mafonction x y = blabla Si on reprend la fonction map, on remarque qu'on l'utilise très souvent pour définir une fonction qui prend une liste et la donne en argument à `map f`, où f est une fonction. On va donc essayer de créer une fonction mapF pour factoriser ce code : mapF prend en argument une fonction, et renvoie une fonction qui prend en argument une liste et renvoie la liste transformée avec la fonction :::haskell foisDeux xs = map (*2) xs plusUn xs = map (+1) xs mapF f = (\xs -> map f xs) -- on peut redéfinir nos fonctions en utilisant mapF foisDeux' = mapF (*2) plusUn' = mapF (+1) On remarque que l'on n'a plus à mentionner la liste qui est transformée : c'est un style de programmation différent, où au lieu de se concentrer sur les données qu'on prend en argument, manipule et renvoie, on prend un autre point de vue et on crée des transformations (des fonctions) en combinant des fonctions de base avec des fonctions d'ordre supérieur comme mapF. On peut aussi créer les fonctions filterF et foldrF, qui sont les équivalents de filter et foldr : :::haskell filterF p = (\xs -> filter p xs) foldrF f k = (\xs -> foldr f k xs) somme = foldrF (+) 0 -- Somme des éléments d'une liste pairs = filterF even -- Renvoie tous les éléments pairs Pour vous exercer, essayez de deviner les types de mapF et filterF : :::haskell mapF :: (a -> b) -> ([a] -> [b]) filterF :: (a -> Bool) -> ([a] -> [a]) #### L'application partielle Maintenant que vous avez recodé vos fonctions d'ordre supérieur préférées pour penser en termes de transformations, voilà la bonne nouvelle : vous avez fait tout ça pour rien. En effet, il existe un mécanisme appelé l'application partielle qui permet de ne pas avoir à coder les fonctions mapF, filterF, etc. Prenons la fonction f ci-dessous comme exemple : :::haskell f :: String -> Int -> String f x n = concat (replicate n x) Quand on applique la fonction (c'est-à-dire on l'appelle) sans avoir fourni le bon nombre d'arguments, on obtient une fonction qui prend les arguments manquants et renvoie le résultat : Prelude> let g = f "NI! " Prelude> :t g g :: Int -> String Prelude> g 5 "NI! NI! NI! NI! NI!" Ici, en définissant g, on a appliqué partiellement la fonction f, ce qui a donné une fonction qui, quand on lui donne un nombre, affiche ce nombre de fois "NI! ". On se rend compte qu'on peut utiliser l'application partielle pour remplacer mapF : :::haskell foisDeux = map (*2) -- c'est la même chose que : foisDeux xs = map (*2) xs On peut faire de même pour filterF et foldrF. Finalement, cela veut dire que quand on a des fonctions définies comme `fonction x = f a b c d x`, on peut enlever l'argument et se retrouver avec `fonction = f a b c d`. Par exemple, essayez de réécrire les fonctions suivantes : :::haskell somme xs = foldr (+) 0 xs produit xs = foldr (*) 1 xs impairs xs = filter odd xs plusUn xs = map (+1) xs listesFoisDeux xss = map (\xs -> map (*2) xs) xss On obtient : :::haskell somme = foldr (+) 0 produit = foldr (*) 1 impairs = filter odd plusUn = map (+1) listesFoisDeux = map (map (*2)) #### Des fonctions qui renvoient des fonctions En fait, il n'y a aucune différence entre les fonctions map et mapF. Cela vient en fait de la manière dont l'application partielle fonctionne. Regardons les types et les définitions de map et mapF : :::haskell map :: (a -> b) -> [a] -> [b] map = (\f xs -> ... ) mapF :: (a -> b) -> ([a] -> [b]) mapF = (\f -> (\xs -> ... )) La seule différence entre ces deux fonctions est une paire de parenthèses autour de `[a] -> [b]` et deux fonctions anonymes imbriquées au lieu d'une. Ces deux fonctions seraient donc les mêmes si les fonctions à plusieurs arguments étaient des fonctions qui prennent un argument et renvoient des fonctions à un argument, et ainsi de suite, jusqu'à renvoyer le résultat. C'est exactement ce qui se produit : quand on écrit le type `a -> b -> c -> d`, il est en réalité compris comme `a -> (b -> (c -> d))`. De même, quand on écrit une fonction anonyme `(\a b c -> quelque chose)`, c'est comme si on écrivait `(\a -> (\b -> (\c -> quelque chose)))`. Et on a la même chose pour l'application de fonction : au lieu d'écrire `((f a) b) c` (c'est-à-dire appliquer la fonction f à a, appliquer la fonction renvoyer à b, puis à c, ce qui donnerait le "quelque chose" de notre fonction définie plus haut), on peut simplement écrire `f a b c`. Vous pouvez voir que c'est comme ça que fonctionne l'application partielle : quand on donne seulement un argument à une fonction, elle renvoie bien une autre fonction qui prend les arguments restants et renvoie le résultat. On dit que les fonctions sont *curryfiées* (du nom d'[Haskell Curry](http://en.wikipedia.org/wiki/Haskell_Curry "http://en.wikipedia.org/wiki/Haskell_Curry")) Après ce passage un peu abstrait, nous allons voir quelques applications intéressantes de cette idée. ### Quelques fonctions d'ordre supérieur #### Quelques fonctions de base L'opérateur **$** est plutôt utile. Pourtant, sa définition est très simple : :::haskell f $ x = f x Cet opérateur correspond donc à l'application de fonction. Cependant, il y a une grosse différence entre les deux : ils n'ont pas la même priorité. On se sert surtout de $ pour supprimer des parenthèses, comme dans l'exemple suivant (`Just` est en réalité un constructeur, mais les constructeurs peuvent s'utiliser exactement de la même manière qu'une fonction). :::haskell plusMaybe a b = Just (a+b) -- on peut le remplacer par : plusMaybe a b = Just $ a + b $ a aussi une utilité avec la section d'opérateurs : par exemple, imaginons qu'on ait une liste de fonctions, et qu'on veuille la liste des valeurs renvoyées par chacune de ces fonctions quand on leur donne une valeur en argument : :::haskell fonctions = [(+1),(*2),(3-),(2/),abs] resultats = map (\f -> f 5) fonctions -- on peut aussi écrire : resultats = map ($ 5) fonctions Une autre fonction parfois utile est la fonction flip. Vous devriez pouvoir deviner ce qu'elle fait simplement avec son type, qui est `flip :: (a -> b -> c) -> (b -> a -> c)` : la fonction flip renverse les arguments d'une fonction. En fait, on peut aussi noter le type de la fonction comme `flip :: (a -> b -> c) -> b -> a -> c`. Cela veut dire qu'on peut écrire des choses comme ceci : :::haskell reverse = foldl (flip (:)) [] -- Une définition de reverse sans utiliser de fonction anonyme flipFilter = flip filter -- la fonction filter avec ses arguments renversés selectEntiers = flipFilter [0..] -- on peut en fait écrire : selectEntiers = flip filter [0..] Mais on peut aussi passer une fonction à plus de deux arguments à flip, et l'effet de flip sera d'inverser les deux premiers arguments (ça se voit très bien en regardant le type). Dans le cas de flip, la curryfication des fonctions est très utile, puisqu'elle permet de ne pas avoir à écrire un flip dépendant du nombre d'arguments de la fonction, et de fournir sans problème un argument à la fonction après avoir appelé flip. Finalement, vous pouvez écrire vous-même une définition pour flip : :::haskell flip' f a b = f b a #### Composer des fonctions Une fonction très utile (et que vous rencontrerez souvent si vous voulez lire du code) est l'opérateur `.`. On note `f . g` la *composition* des fonctions f et g. Vous avez peut-être déjà rencontré cette opération en maths, notée `f o g`. En fait, on a `(f . g) x = f (g x)`. Vous comprendrez mieux comment ça marche avec quelques exemples : :::haskell foisDeux = (*2) plusUn = (+1) maFonction x = 2*x+1 -- on peut aussi écrire : maFonction' = (+1) . (*2) Maintenant, vous pouvez regarder le type de ., et essayer de comprendre (comme avec flip) comment cet opérateur interagit avec les fonctions qui prennent plus d'un argument. On peut bien sûr mettre plus de 2 fonctions à la suite : :::haskell sommeCarresPairs xs = sum . map (^2) . filter even $ xs -- on pourrait aussi écrire sommeCarresPairs' = sum . map (^2) . filter even Cette façon d'écrire les fonctions, sans indiquer les arguments, est assez utilisée en Haskell. Dans beaucoup de cas, ça rend le code plus concis, et facile à lire (plus besoin de faire attention aux 3 niveaux de parenthèses imbriquées. Mais dans certains cas, cela peut donner du code complètement illisible, où il est impossible de deviner ce que fait un enchaînement de points. Par exemple, regardons le code suivant, qui teste si un élément est dans une liste : :::haskell mem x xs = any (== x) xs -- On transforme ça simplement en : mem' x = any (==x) -- Cette fonction est encore raisonnablement lisible -- Mais on peut pousser le style plus loin : mem'' = any . (==) Si vous essayez de comprendre comment marche la fonction `mem''`, vous vous apercevrez qu'elle fait exactement la même chose que la fonction `mem`. Cependant, cette dernière version est totalement illisible. C'est très pratique pour gagner un concours où il faut un code le plus court possible, mais si vous n'êtes pas dans ce cas, pensez à ceux qui vont relire votre code (vous y compris). Il ne faut surtout pas hésiter à donner des noms à des résultats ou des fonctions intermédiaires pour clarifier le fonctionnement de la fonction. Certains s'amusent à essayer de réécrire (ou d'écrire directement) du code de cette façon. Juste pour l'exemple, voici quelques opérateurs effrayants tirés de la page [http://haskell.org/haskellwiki/Pointfree](http://haskell.org/haskellwiki/Pointfree "http://haskell.org/haskellwiki/Pointfree") : :::haskell owl = ((.)$(.)) dot = ((.).(.)) swing = flip . (. flip id) Ce chapitre sur la programmation fonctionnelle est terminée. Les fonctions d'ordre supérieur sont utilisées partout en Haskell, et si vous voyez quelque chose qui se répète, votre premier réflexe doit être de chercher à factoriser le code, parce que moins de code, c'est moins de bugs, et c'est un programme plus facile à comprendre. De plus, cela vous entraînera à appliquer les techniques vues dans ce chapitre. Dans le prochain chapitre, on s'attaque à deux choses très importantes : les types et les classes de types. Alors que jusqu'à maintenant, vous n'avez fait qu'utiliser les types prédéfinis, vous allez apprendre à créer vos propres types, et à les utiliser pour, par exemple, manipuler des opérations mathématiques... et pourquoi pas créer un interpréteur pour un petit langage de programmation ?