URL: https://linuxfr.org/users/guillaum/journaux/haskell-evaluation-paresseuse Title: Haskell -- Évaluation paresseuse Authors: Guillaum Date: 2016年05月03日T12:31:10+02:00 License: CC By-SA Tags: haskell et lazy Score: 37 Bonjour, Je voulais vous parler d'[évaluation paresseuse](https://en.wikipedia.org/wiki/Lazy_evaluation), en me servant comme support du langage [Haskell](https://haskell.org). L'évaluation paresseuse c'est juste le summum de la procrastination, reporter à demain (ou jamais) ce que tu n'as pas besoin de faire aujourd'hui. En haskell, une fonction n'est évaluée que si la valeur de retour est nécessaire pour évaluer immédiatement un autre résultat. Je ne vous parlerai pas des avantages ou inconvénient de cela, mais je vais plutôt donner des exemples que je trouve amusant. # Opérateur à court-circuit # Dans tous les langages de programmation il y a des opérateurs à court-circuit, comme le `&&` / `and`. Exemple en Python : ```python resultat = longCalculA(argA) and longCalculB(argB) ``` `longCalculB` ne sera effectué que si longCalculA renvoie `True`. Dans ce cas là, le résultat de `and` est défini par le résultat de `longCalculB`. Mais si `longCalculA` renvoie `False`, alors le résultat de `longCalculB` n'est pas nécessaire, et il ne sera donc pas calculé. Cet opérateur `and` est un cas particulier du langage Python et il est impossible de l’implémenter en Python pur. Essayons : ```python def myAnd(a, b): if a == False: return False else: return b resultat = myAnd(longCalculA(argA), longCalculB(argB)) ``` Bien que le résultat sera le même, les deux fonctions `longCalculA` et `longCalculB` seront appelées *avant* l'appel à `myAnd`, et donc une perte d'efficacité très claire. En Haskell : ```haskell myAnd a b = if a == False then False else b resultat = myAnd (longCalculA argA) (longCalculB argB) ``` Ici les calculs ne sont pas effectués tant que ce n'est pas nécessaire. Ainsi pour connaitre le `resultat`, il faut regarder la valeur de `longCalculA` (et donc effectuer le calcul), mais si celui-ci est `False`, alors la valeur de `b` importe peu et le calcul ne sera jamais effectué. # Visualisation # Pour les besoins de cet exemple j'ai crée une fonction `longId` qui met du temps (~ une seconde) à renvoyer la valeur passée en paramètre, j'ajoute les temps en commentaire sur chaque ligne : ```haskell *Long> print (longId 10) -- 1s 10 *Long> print (longId "Hello") -- 1s "Hello" ``` On va s'amuser un peu avec, que se passe-il si on applique la fonction `longId` sur tous les éléments de `1` à `10` : ```haskell *Long> print (map longId [1..10]) -- 10 secondes [1,2,3,4,5,6,7,8,9,10] ``` En fait, de façon amusante, les chiffres apparaissent les uns après les autres, un par seconde. En fait la fonction `print` consomme les éléments du résultat un par un et est capable de les afficher quand ils arrivent. Cependant, combien de temps prend le calcul de la longueur de la liste ? ```haskell *Long> print (length (map longId [1..10])) -- instantané 10 ``` C'est instantané, car il n'est pas nécessaire d'évaluer les cellules de la liste pour connaitre la longueur. Autres exemples, avec la fonction `elem` qui teset si un élément est dans la liste : ```haskell *Long> print (elem 1 (map longId [1..10])) -- 1s True *Long> print (elem 5 (map longId [1..10])) -- 5s True *Long> print (elem 10 (map longId [1..10])) -- 10s True ``` Les éléments de la liste qui ne sont pas testés ne sont pas calculés. Nous allons pousser un peu plus grâce à l'outil `:sprint` du shell ghci. Celui-ci permet de voir les valeurs évaluées et celles qui ne le sont pas encore. Nous allons partir d'une liste toute simple : ```haskell *Long> let l = map longId [1..10] :: [Int] ``` (Pour des raisons techniques je force le type de la liste à une liste d'entiers `[Int]`). Comment est évalué `l` ?: ```haskell *Long> :sprint l l = _ ``` Ici `_` signifie que ce n'est pas évalué. Prenons maintenant les 3 premiers éléments de la liste, sans les afficher. ```haskell *Long> print (length (take 3 l)) -- instantané 3 *Long> :sprint l l = _ : _ : _ : _ ``` Ici on obtient une suite de cellules de liste, liées ensemble par `(:)`. Il y a 4 éléments, les 3 premiers et la suite de la liste. Notez que les éléments ne sont pas évalués. Nous allons commencer à en évaluer quelques-un, le premier et le dernier. ```haskell *Long> print (head l) -- 1s 1 *Long> :sprint l l = 1 : _ : _ : _ *Long> print (last l) -- 1s 10 *Long> :sprint l l = [1,_,_,_,_,_,_,_,_,10] *Long> ``` L'évaluation du premier élément apparaît dans `sprint`, le `_` est remplacé par `1`. L'évaluation du dernier élément force l'évaluation de toutes les cellules de la liste (mais pas de leur contenu) ainsi que du contenu de la dernière cellule. Les deux évaluations n'ont prise chacune qu'une seule seconde, temps nécessaire pour évaluer la première ou dernière cellule. Nous allons conclure : ```haskell *Long> print (sum l) -- 8 secondes 55 *Long> :sprint l l = [1,2,3,4,5,6,7,8,9,10] ``` Notez que cela ne prend que 8 secondes, puisque la première et dernière cellule sont déjà évaluées. # Fun et brain melting # Nous allons nous intéresser à une fonction totalement inutile qui calcul une normalisation d'une liste de nombre en divisant les éléments de la liste par la somme des éléments de cette liste, soit : ```haskell *Main> f [1,2,3,4] [0.1,0.2,0.3,0.4] ``` (ici la somme fait `10`). Une façon simple d'écrire cette fonction est la suivante : ```haskell f l = let s = sum l in map (/s) l ``` En premier lieu on calcule la somme de la liste avec `s = sum l` et on applique la division par `s`, `(/s)` sur chaque élément de la liste avec la fonction `map`. La liste est parcourue deux fois, une fois pour faire la somme, et une fois pour faire la division de chaque élément. Ne pourrait-on pas faire cela en un seul parcours pour s'amuser ? Pour cela nous allons introduire une nouvelle fonction `g` qui fait deux choses : elle calcule le résultat et elle renvoie la somme. Cependant elle prend la somme utilisée pour la division en paramètre. Exemple : ```haskell *Main> g 10 [1,2,3,4] ([0.1,0.2,0.3,0.4],10.0) *Main> g 100 [1,2,3,4] ([1.0e-2,2.0e-2,3.0e-2,4.0e-2],10.0) ``` Dans le premier exemple, la somme passée est `10` et le résultat est le bon. Dans le second cas, la somme passée est `100`, donc la liste de résultats a des valeurs `10` fois trop petites, mais par contre la somme retournée est bien 10. Je laisse l'écriture de la fonction `g` en tant qu'exercice au lecteur, elle n'est pas importante. Écrivons maintenant `f` : ```haskell f l = let s = sum l (res, s') = g s l in res ``` Ici nous calculons la somme grâce à `s = sum l`, nous appelons la fonction `g` en lui passant la somme et la liste et nous récupérons le résultat et la somme `s'` calculée par `g`, pour enfin renvoyer le résultat `let ... in res`. La liste est toujours parcourue deux fois (dans `sum` et dans `g`). Ici `s` et `s'` représentent la même valeur, la somme de la liste. On pourrait même envisager de remplacer l'un par l'autre : ```haskell f l = let s = sum l (res, s') = g s' l in res ``` Et ici le calcul de `s` ne sert plus à rien... : ```haskell f l = let (res, s') = g s' l in res ``` Alors pourquoi cela fonctionne, sachant que `s'` est autant un paramètre de `g` qu'un résultat ? La fonction `g` va se contenter de crée une liste qui contient : $$ [l_0 / s, l_1 / s, l_2 / s, ...] $$ Mais elle contient les fonctions non évaluées. Ainsi la valeur de `s` n'est pas nécessaire pour construire la liste. Bien que pas encore calculée, elle peut être utilisée dans des expressions à condition que son calcul ne dépende pas du résultat de ces expressions. Une fois que `g` se termine, la valeur de `s` est bien définie, et donc l'évaluation des cellules de la liste de résultat de `g` peut être effectuée. Bref, moi je trouve cela marrant. Et vous ?

AltStyle によって変換されたページ (->オリジナル) /