Haskell comme un vrai!

Haskell à s'en faire griller les neurones

Magritte pleasure principle

tlpl: Un tutoriel très court mais très dense pour apprendre Haskell.

Merci à :

Table of Content

Je pense vraiment que tous les développeurs devraient apprendre Haskell. Peut-être pas devenir des ninjas d’Haskell, mais au moins savoir ce que ce langage a de particulier. Son apprentissage ouvre énormément l’esprit.

La plupart des langages partagent les mêmes fondements :

  • les variables
  • les boucles
  • les pointeurs1
  • les structures de données, les objets et les classes

Haskell est très différent. Ce langage utilise des concepts dont je n’avais jamais entendu parler avant. Beaucoup de ces concepts pourront vous aider à devenir un meilleur développeur.

Plier son esprit à Haskell peut être difficile. Ce le fut pour moi. Dans cet article, j’essaye de fournir les informations qui m’ont manquées lors de mon apprentissage.

Cet article sera certainement difficile à suivre. Mais c’est voulu. Il n’y a pas de raccourci pour apprendre Haskell. C’est difficile. Mais je pense que c’est une bonne chose. C’est entre autres parce qu’Haskell est difficile qu’il est intéressant.

La manière conventionnelle d’apprendre Haskell est de lire deux livres. D’abord “Learn You a Haskell” et ensuite “Real World Haskell”. Je pense aussi que c’est la bonne manière de s’y prendre. Mais apprendre même un tout petit peu d’Haskell est presque impossible sans se plonger réellement dans ces livres.

Cet article fait un résumé très dense et rapide des aspects majeurs d’Haskell. J’y ai aussi rajouté des informations qui m’ont manqué pendant l’apprentissage de ce langage.

Pour les francophones : je suis désolé. Je n’ai pas eu le courage de tout retraduire en français. Sachez cependant que si vous êtes plusieurs à insister, je ferai certainement l’effort de traduire l’article en entier. Et si vous vous sentez d’avoir une bonne âme je ne suis pas contre un peu d’aide. Les sources de cet article sont sur github.

Cet article contient cinq parties :

  • Introduction : un exemple rapide pour montrer qu’Haskell peut être facile.
  • Les bases d’Haskell : La syntaxe et des notions essentielles
  • Partie difficile :
    • Style fonctionnel : un exemple progressif, du style impératif au style fonctionnel ;
    • Types : la syntaxe et un exemple d’arbre binaire ;
    • Structure infinie : manipulons un arbre infini !
  • Partie de difficulté infernale :
    • Utiliser les IO : un exemple très minimal ;
    • Le truc des IO révélé : les détails cachés d’IO qui m’ont manqués
    • Les monades : incroyable à quel point on peut généraliser
  • Appendice :
    • Revenons sur les arbres infinis : une discussion plus mathématique sur la manipulation d’arbres infinis.
Note: Chaque fois que vous voyez un séparateur avec un nom de fichier se terminant par lhs, vous pouvez cliquer sur le nom de fichier et télécharger le fichier. Si vous sauvegardez le fichier sour le nom filename.lhs, vous pouvez l’exécuter avec : 
runhaskell filename.lhs

Certains ne marcheront pas, mais la majorité vous donneront un résultat. Vous devriez voir un lien juste en dessous.

01_basic/10_Introduction/00_hello_world.lhs

Introduction

Installation

Aujourd’huil je considère que la manière la plus aisée d’installer Haskell est d’utiliser stack.

Il y a d’autres manières d’installer Haskell sur votre système, vous pouvez en savoir plus en visitant haskell.org ou haskell-lang.org

Outils:

  • ghc: Compilateur similaire à gcc pour le langage C.
  • ghci: Console Haskell interactive (Read-Eval-Print Loop)
  • runhaskell: Exécuter un programme sans le compiler. Pratique mais très lent comparé aux programmes compilés.

Ne soyez pas effrayés!

The Scream

Beaucoup de livres/articles sur Haskell commencent par présenter des formules ésotériques (Algorithmes de tri rapide, suite de Fibonacci, etc…). Je ferai l’exact opposé En premier lieu je ne vous montrerai pas les super-pouvoirs d’Haskell. Je vais commencer par les similarités avec les autres langages de programmation. Commençons par l’indispensable “Hello World!”.

Pour l’exécuter, vous pouvez enregistrer ce code dans un fichier hello.hs et:

ou si vous utilisez stack lancez d’abord stack setup et ensuite :

Vous pouvez également télécharger la source Haskell littérale. Vous devriez voir un lien juste au dessus du titre de l’introduction. Téléchargez ce fichier en tant que 00_hello_world.lhs et:

01_basic/10_Introduction/00_hello_world.lhs

01_basic/10_Introduction/10_hello_you.lhs

Maintenant, un programme qui demande votre nom et répond “Hello” suivit du nom que vous avez entré:

Premièrement, comparons ce code avec ceux de quelques langages de programmation impératif:

La structure est la même, mais il y a quelques différences de syntaxe. La partie principale de ce tutoriel sera consacrée à expliquer cela.

En Haskell il y a une fonction main tous les objets ont un type. Le type de main est IO (). Cela veut dire que main causera des effets secondaires.

Rappelez-vous just que Haskell peut ressembler énormément aux principaux langages impératifs.

01_basic/10_Introduction/10_hello_you.lhs

01_basic/10_Introduction/20_very_basic.lhs

Les bases de Haskell

Picasso minimal owl

Avant de continuer, vous devez êtres avertis à propos de propriétés essentielles de Haskell.

Fonctionnel

Haskell est un langage fonctionnel Si vous avez déjà travaillé avec un langage impératif, vous devrez apprendre beaucoup de nouvelles choses. Heureusement beaucoup de ces nouveaux concepts vous aidera à programmer même dans un langage impératif.

Typage Statique Intelligent

Au lieu de bloquer votre chemin comme en C, C++ ou Java, le système de typage est ici pour vous aider.

Pureté

Généralement vos fonctions ne modifieront rien du le monde extérieur. Cela veut dire qu’elles ne peuvent pas modifier la valeur d’une variable, lire du texte entré par un utilisateur, écrire sur l’écran, lancer un missile. D’un autre coté, avoir un code parallèle devient très facile. Haskell rend très clair où les effets apparaissent et où le code est pur. De plus, il devient beaucoup plus aisé de raisonner sur son programme. La majorité des bugs seront évités dans les parties pures de votre programme.

En outre, les fonctions pures suivent une loi fondamentale en Haskell:

Appliquer une fonction avec les mêmes paramètres retourne toujours la même valeur.

Paresse

La paresse par défaut est un choix de conception de langage très rare. Par défaut, Haskell évalue quelque chose seulement lorsque cela est nécessaire. En conséquence, cela fournit un moyen très élégant de manipuler des structures infinies, par exemple.

Un dernier avertissement sur comment vous devriez lire le code Haskell. Pour moi, c’est comme lire des papiers scientifiques. Quelques parties sont très claires, mais quand vous voyez une formule, concentrez-vous dessus et lisez plus lentement. De plus, lorsque vous apprenez Haskell, cela n’importe vraiment pas si vous ne comprenez pas les détails syntaxiques. Si vous voyez un >>=, <$>, <- ou n’importe quel symbole bizarre, ignorez-les et suivez le déroulement du code.

Déclaration de fonctions

Vous avez déjà dû déclarer des fonctions comme cela:

En C:

En JavaScript:

En Python:

En Ruby:

En Scheme:

Finalement, la manière de faire de Haskell est:

Très propre. Aucune parenthèse, aucun def.

N’oubliez pas, Haskell utilise beaucoup les fonctions et les types. C’est très facile de les définir. La syntaxe a été particulièrement réfléchie pour ces objets.

Un exemple de type

Même si ce n’est pas obligatoire, les informations de type pour les fonctions sont habituellement déclarées explicitement. Ce n’est pas indispensable car le compilateur est suffisamment intelligent pour le déduire à votre place. Cependant, c’est une bonne idée car cela montre bien l’intention du développeur et facilite la compréhension.

Jouons un peu. On déclare le type en utilisant ::

~ runhaskell 20_very_basic.lhs
13

01_basic/10_Introduction/20_very_basic.lhs

01_basic/10_Introduction/21_very_basic.lhs

Maintenant essayez

Vous devriez avoir cette erreur:

21_very_basic.lhs:6:23:
    No instance for (Fractional Int)
      arising from the literal `4.2'
    Possible fix: add an instance declaration for (Fractional Int)
    In the second argument of `f', namely `4.2'
    In the first argument of `print', namely `(f 2.3 4.2)'
    In the expression: print (f 2.3 4.2)

Le problème est que 4.2 n’est pas de type Int (NDT: Il n’est pas un entier)

01_basic/10_Introduction/21_very_basic.lhs

01_basic/10_Introduction/22_very_basic.lhs

La soulution: ne déclarez pas de type pour f pour le moment et laissez Haskell inférer le type le plus général pour nous:

Maintenant, ça marche! Heureursement, nous n’avons pas à déclarer un nouvelle fonction pour chaque type différent. Par exemple, en C, vous auriez dû déclarer un fonction pour int, pour float, pour long, pour double, etc…

Mais quel type devons nous déclarer? Pour découvrir le type que Haskell a trouvé pour nous, lançons ghci:


% ghci
GHCi, version 7.0.4: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude> let f x y = x*x + y*y
Prelude> :type f
f :: Num a => a -> a -> a

Hein? Quel ce type étrange?

Num a => a -> a -> a

Premièrement, concentrons-nous sur la partie de droite: a -> a -> a. Pour le comprendre, regardez cette liste d’exemples progressifs:

Le type écrit Son sens
Int Le type Int
Int -> Int Le type de la fonction qui prend un Int et retourne un Int
Float -> Int Le type de la fonction qui prend un Float et retourne un Int
a -> Int Le type de la fonction qui prend n’importe quel type de variable et retourne un Int
a -> a Le type de la fonction qui prend n’importe quel type a et retourne une variable du même type a
a -> a -> a Le type de la fonction qui prend deux arguments de n’importe quel typea et retourne une variable de type a

Dans le type a -> a -> a, la lettre a est une variable de type. Cela signifie que f est une fonction avec deux arguments et que les deux arguments et le résultat ont le même type. La variable de type a peut prendre de nombreuses valeurs différentes Par exemple Int, Integer, Float…

Donc à la place d’avoir un type forcé comme en C et de devoir déclarer une fonction pour int, long, float, double, etc., nous déclarons une seule fonction comme dans un langage typé de façon dynamique.

C’est parfois appelé le polymorphisme paramétrique. C’est aussi appelé avoir un gâteau et le manger.

Généralement a peut être de n’importe quel type, par exemple un String ou un Int, mais aussi des types plus complexes comme Trees, d’autres fonctions, etc. Mais ici notre type est préfixé par Num a =>.

Num est une classe de type. Une classe de type peut être comprise comme un ensemble de types Num contient seulement les types qui se comportent comme des nombres. Plus précisement, Num est une classe qui contient des types qui implémentent une liste spécifique de fonctions, en particulier (+) et (*).

Les classes de types sont une structure de langage très puissante. Nous pouvons faire des trucs incroyablement puissants avec. Nous verrons cela plus tard.

Finalement, Num a => a -> a -> a signifie:

soit a un type qui appartient à la classe Num. C’est une fonction qui prend une variable de type a et retourne une fonction de type (a -> a)

Oui, c’est étrange. En fait, en Haskell aucune fonction ne prend réellement deux arguments. Au lieu de cela toutes les fonctions n’ont qu’un argument unique. Mais nous retiendrons que prendre deux arguments est équivalent à n’en prendre qu’un et à retourner une fonction qui prend le second argument en paramètre.

Plus précisement f 3 4 est équivalent à (f 3) 4. Remarque: f 3 est une fonction:

f :: Num a => a -> a -> a

g :: Num a => a -> a
g = f 3

g y ⇔ 3*3 + y*y

Une autre notation existe pour les fonctions. La notation lambda nous autorise à créer des fonctions sans leur assigner un nom. On les appelle des fonctions anonymes. nous aurions donc pu écrire:

g = \y -> 3*3 + y*y

Le \ esst utilisé car il ressemble à un λ et est un caractère ASCII.

Si vous n’êtes pas habitué à la programmation fonctionnelle, votre cerveau devrait commencer à chauffer Il est temps de faire une vraie application.

01_basic/10_Introduction/22_very_basic.lhs

01_basic/10_Introduction/23_very_basic.lhs

Mais juste avant cela, nous devrions vérifier que le système de type marche comme nous le supposons:

Cela fonctionne, car 3 est une représentation valide autant pour les nombres fractionnaires comme Float que pour les entiers. Comme 2.4 est un nombre fractionnaire, 3 est interprété comme une autre nombre fractionnaire

01_basic/10_Introduction/23_very_basic.lhs

01_basic/10_Introduction/24_very_basic.lhs

Si nous forçons notre fonction à travailler avec des types différents, le test échouera:

Le compilateur se plaint. Les deux paramètres doivent avoir le même type.

Si vous pensez que c’est une mauvaise idée et que le compilateur devrait faire la transformation depuis un type à un autre pour vous, vous devriez vraiment regarder cette vidéo géniale (et amusante): WAT (NDT: En Anglais)

01_basic/10_Introduction/24_very_basic.lhs

Notions essentielles

Kandinsky Gugg

Je vous suggère de seulement survoler cette partie Pensez-y seulement comme à une référence. Haskell a beaucoup de caractèristiques Il manque beaucoup d’informations ici. Revenz ici si la notation vous semble étrange.

J’utilise le symbole ⇔ pour signifier que deux expressions sont équivalentes. C’est une notation extérieure, ⇔ n’existe pas en Haskell. Je vais aussi utiliser le symoble ⇒ quelle est la valeur que retourne une fonction.

Notations

Arithmétique 
3 + 2 * 6 / 3 ⇔ 3 + ((2*6)/3)
Logique 
True || False ⇒ True
True && False ⇒ False
True == False ⇒ False
True /= False ⇒ True  (/=) est l'opérateur pour "différent de"
Puissances 
x^n     pour n un entier (comprenez Int ou Integer)
x**y    pour y tout type de nombre (Float par exemple)

Integer n’a aucune limite à part la capacité de votre machine:

4^103
102844034832575377634685573909834406561420991602098741459288064

Yeah! Et aussi les nombres rationnels! Mais vous avez besoin d’importer le module Data.Ratio

$ ghci
....
Prelude> :m Data.Ratio
Data.Ratio> (11 % 15) * (5 % 3)
11 % 9
Listes 
[]                      ⇔ liste vide
[1,2,3]                 ⇔ Liste d'entiers
["foo","bar","baz"]     ⇔ Liste de chaînes de caractères
1:[2,3]                 ⇔ [1,2,3], (:) ajoute un élément au début
1:2:[]                  ⇔ [1,2]
[1,2] ++ [3,4]          ⇔ [1,2,3,4], (++) concaténation de deux listes
[1,2,3] ++ ["foo"]      ⇔ ERREUR String ≠ Integral
[1..4]                  ⇔ [1,2,3,4]
[1,3..10]               ⇔ [1,3,5,7,9]
[2,3,5,7,11..100]       ⇔ ERREUR! Je ne suis pas si intelligent!
[10,9..1]               ⇔ [10,9,8,7,6,5,4,3,2,1]
Chaînes de caractères

En Haskell les chaînes de caractères sont des listes de Char.

'a' :: Char
"a" :: [Char]
""  ⇔ []
"ab" ⇔ ['a','b'] ⇔  'a':"b" ⇔ 'a':['b'] ⇔ 'a':'b':[]
"abc" ⇔ "ab"++"c"

Remarque: Dans un vrai code vous n’utiliserez pas des listes de char pour représenter du texte. Vous utiliserez plus souvent Data.Text à la place. Si vous voulez représenter un chapelet de caractères ASCII, vous utiliserez Data.ByteString.

Tuples

Le type d’un couple est (a,b). Les éléments d’un tuple peuvent avoir des types différents.

-- tous ces tuples sont valides
(2,"foo")
(3,'a',[2,3])
((2,"a"),"c",3)

fst (x,y)       ⇒  x
snd (x,y)       ⇒  y

fst (x,y,z)     ⇒  ERROR: fst :: (a,b) -> a
snd (x,y,z)     ⇒  ERROR: snd :: (a,b) -> b
Traiter avec les parenthèses

Pour enlever des parenthèses vous pouvez utiliser deux fonctions: ($) et (.).

-- Par défaut:
f g h x         ⇔  (((f g) h) x)

-- le $ remplace les parenthèses depuis le $
-- jusqu'à la fin de l'expression.
f g $ h x       ⇔  f g (h x) ⇔ (f g) (h x)
f $ g h x       ⇔  f (g h x) ⇔ f ((g h) x)
f $ g $ h x     ⇔  f (g (h x))

-- (.) permet de faire des compositions de fonctions
(f . g) x       ⇔  f (g x)
(f . g . h) x   ⇔  f (g (h x))

01_basic/20_Essential_Haskell/10a_Functions.lhs

Notations utiles pour les fonctions

Juste un mémo:

x :: Int            ⇔ x est de type Int
x :: a              ⇔ x peut être de n'importe quel type
x :: Num a => a     ⇔ x peut être de n'importe quel type a
                      tant qu' a appartient à la classe de type Num 
f :: a -> b         ⇔ f est une fonction qui prend un a et retourne un b
f :: a -> b -> c    ⇔ f est une fonction qui prend un a et retourne un (b→c)
f :: (a -> b) -> c  ⇔ f est une fonction qui prend un (a→b) et retourne un c

Rappelez-vous que définir le type d’une fonction avant sa déclaration n’est pas obligatoire. Haskell infère le type le plus général pour vous. Mais c’est considéré comme une bonne pratique.

Notation Infixée

Remarquez que ^ utilise une notation infixée. Pour chaque opérateur infixe il y a une notation préfixée associée. Vous devez juste l’écrire entre parenthèses.

Nous pouvons enlever le x dans les parties de gauche et de droite! On appelle cela la η-réduction

Rmarquez qu nous pouvons déclarer des fonctions avec ' dans leur nom. Exemples:

square ⇔ square' ⇔ square'' ⇔ square'''

Tests

Une implémentation de la fonction absolue.

Remarque: la notation de Haskell pour le if .. then .. else ressemble plus à l’opérateur ¤?¤:¤ en C. Le else est obligatoire.

Une version équivalente:

Avertissement: l’indentation est importante en Haskell. Comme en Python, une mauvaise indentation peut détruire votre code!

01_basic/20_Essential_Haskell/10a_Functions.lhs

La Partie Difficile

La partie difficile peut maintenant commencer.

Le style fonctionnel

Biomechanical Landscape by H.R. Giger

Dans cette section, je vais vous donner un court exemple de l’impressionante capacité de remaniement de Haskell. Nous allons sélectionner un problème et le résoudre à la manière d’un langage impératif standard. Ensuite, je ferais évoluer le code. Le résultat final sera plus élégant et plus facile à adapter.

résolvons les problèmes suivants:

Soit une liste d’entiers, retourner la somme des nombres pairs de cette liste.

exemple: [1,2,3,4,5] ⇒ 2 + 4 ⇒ 6

Pour montrer les différences entre les approches fonctionnelle et impérative, je vais commencer par donner la solution impérative (en JavaScript):

En Haskell, en revanche, nous n’avons pas de variables ou un boucle for. Une des solutions pour parvenir au même résultat sans boucles est d’utiliser la récursion.

Remarque: La récursion est souvent perçue comme lente dans les langages impératifs. Mais ce n’est généralement pas le cas en programmation fonctionnelle. La plupart du temps Haskell gérera les fonctions récursives efficacement.

Voici la version C de la fonction récursive. Remarquez que je suppose que la liste d’int fini avec la première valeur 0.

Gardez ce code à l’esprit. Nous allons le traduire en Haskell. Premièrement,

even vérifie si un nombre est pair.

head retourne le premier élément d’une liste:

tail retourne tous les éléments d’une liste, sauf le premier:

Remarquez que pour toute liste non-vide l, l ⇔ (head l):(tail l)

02_Hard_Part/11_Functions.lhs

La première solution en Haskell. La fonction evenSum retourne la somme de tous les nombres pairs d’une liste:

Pour tester une fonction nous pouvons utiliser ghci:

% ghci
GHCi, version 7.0.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> :load 11_Functions.lhs
[1 of 1] Compiling Main             ( 11_Functions.lhs, interpreted )
Ok, modules loaded: Main.
*Main> evenSum [1..5]
6

Voici un exemple d’exécution2:

*Main> evenSum [1..5]
accumSum 0 [1,2,3,4,5]
1 est impair
accumSum 0 [2,3,4,5]
2 est pair
accumSum (0+2) [3,4,5]
3 est impair
accumSum (0+2) [4,5]
4 est pair
accumSum (0+2+4) [5]
5 est impair
accumSum (0+2+4) []
l == []
0+2+4
0+6
6

En venant d’un langage impératif, tout devrait vous sembler juste. En fait, beaucoup de choses peuvent être améliorées ici. Tout d’abord, nous pouvons généraliser le type.

02_Hard_Part/11_Functions.lhs

02_Hard_Part/12_Functions.lhs

Ensuite, nous pouvons utiliser des sous-fonctions grâce à where et let. Ansi, notre fonction accumSum ne polluera pas le namespace de notre module

02_Hard_Part/12_Functions.lhs

02_Hard_Part/13_Functions.lhs

Puis on utilise le pattern matching

Qu’est ce que le pattern matching ? Il s’agit d’utiliser des valeurs au lieu de noms de paramètres généraux.

Au lieu d’écrire: foo l = if l == [] then <x> else <y> Vous écrivez tout simplement :

Mais le pattern matching peut aller encore plus loin. Il est également capable d’inspecter les données internes d’un valeur complexe. Nous pouvons ainsi remplacer

par

C’est une caractéristique très utile. Notre code est ainsi plus concis et plus facile à lire.

02_Hard_Part/13_Functions.lhs

02_Hard_Part/14_Functions.lhs

Avec Haskell, nous pouvons simplifier les défitions des fonctions en les η-réduisant . Par exemple, au lieu d’écrire:

Nous pouvons écrire

Utilisons cette méthode pour retirer le l:

02_Hard_Part/14_Functions.lhs

02_Hard_Part/15_Functions.lhs

Fonctions d’ordre supérieur

Escher

Pour rendre les choses plus faciles, nous devrions utiliser des fonctions d’ordre supérieur. Ce sont des fonctions qui prennent des fonctions en paramètres

Voici quelques exemples:

Procédons par étapes.

où

La fonction filter prend une fonction du type (a -> Bool) et une liste de type [a]. Elle retourne une liste qui contient seulement les élements pour qui la fonction a retourné True.

La prochaine étape est d’utiliser une autre technique pour accomplir la même chose qu’une boucle. Nous allons utiliser la fonction foldl pour accumuler une valeur au fur et à mesure que l’on parcoure la liste. La fonction foldl capture un modèle de code général:

    myfunc list = foo initialValue list
    foo accumulated []     = accumulated
    foo tmpValue    (x:xs) = foo (bar tmpValue x) xs

Qui peut être remplacé par:

myfunc list = foldl bar initialValue list

Si vous souhaitez vraiment savoir comment la magie se produit, voici la définition de foldl:

Mais comme Haskell est paresseux, il n’évalue pas (f z x) et le met simplement dans la pile. C’est pourquoi on utilise généralement foldl', une version stricte de foldl, Si vous ne comprenez pas encore ce que paresseux ou strict signifie, ne vous inquiétez pas, suivez le code comme si foldl' et foldl étaient identiques

Maintenant notre version de evenSum devient:

Nous pouvons aussi simplifier cela en utilisant une lambda-notation. Ainsi nous n’avons pas besoin de créer le nom temporaire mySum.

Et bien sûr, nous remarquons que

02_Hard_Part/15_Functions.lhs

02_Hard_Part/16_Functions.lhs

Finalement

foldl' n’est pas la fonction la plus facile à prendre en main. Si vous n’y êtes pas habitué, vous devriez l’étudier un peu.

Pour mieux comprendre ce qui se passe ici, étudions une évaluation étape par étape:

  evenSum [1,2,3,4]
⇒ foldl' (+) 0 (filter even [1,2,3,4])
⇒ foldl' (+) 0 [2,4]
⇒ foldl' (+) (0+2) [4]
⇒ foldl' (+) 2 [4]
⇒ foldl' (+) (2+4) []
⇒ foldl' (+) 6 []
⇒ 6

Une autre fonction d’ordre supérieur utile est (.). Elle correspond à une composition en mathématiques.

Nous pouvons profiter de cet opérateur pour η-réduire notre fonction:

Nous pouvons maintenant renommer certaines parties pour rendre le tout plus clair:

Il est temps de discuter de la direction qu’a pris notre code depuis que nous avons introduit plus d’idiomes fonctionnels. Que gagnons-nous à utiliser des fonctions d’ordre supérieur?

D’abord, vous pourriez penser que la principale différence est la brièveté. Mais en réalité, il s’agit d’une meilleure façon de penser. Supposons que nous voulons modifier légèrement notre fonction, par exemple, pour qu’elle renvoie la somme de tous les carrés pairs des éléments de la liste.

[1,2,3,4] ▷ [1,4,9,16] ▷ [4,16] ▷ 20

Mettre la version 10 à jour est très facile:

Nous avons juste eu à ajouter une autre “fonction de transformation”.

map (^2) [1,2,3,4] ⇔ [1,4,9,16]

La fonction map applique simplementune fonction à tous les élements d’une liste.

Nous n’avons rien modifié à l’intérieur de notre définition de fonction. Cela rend le code plus modulaire. En plus de cela, vous pouvez penser à votre fonction plus mathématiquement. Vous pouvez aussi utilier votre fonction avec d’autres, au besoin: vous pouvez utiliser compose, map, fold ou filter sur notre nouvelle fonction.

Modifier la version 1 est laissé comme un exercice pour le lecteur ☺.

Si vous croyez avoir atteint le bout de la généralisation, vous avez tout faux. Par example, il y a un moyen d’utiliser cette fonction non seulement sur les listes mais aussi sur n’importe quel type récursif. Si vous voulez savoir comment, je vous suggère de lire cet article: Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire by Meijer, Fokkinga and Paterson (NDT: en anglais, mais là vous vous en seriez douté je pense ☺)

Cet exemple montre à quel point la programmation fonctionnelle pure est géniale. Malheureusement, utiliser cet outil n’est pas adapté à tous les besoins. Ou alors un langage qui le premettrait n’a pas encore été trouvé.

Une des grands pouvoirs de Haskell est sa capacité à créer des DSLs (Domain Specific Language, en français : langage spécifique à un domaine) Il est ainsi facile de changer le pardigme de programmation

En fait, Haskell peut très bien vous permettre d’écrire des programmes impératifs. Comprendre cela a été très difficile pour moi lorsque j’apprenais Haskell. Beaucoup d’efforts tendent à expliquer la supériorité de l’approche fonctionnele. Puis lorsque vous commencez à utliser le style impératif en Haskell, Il peut être difficile de comprendre quand et où l’utliser.

Mais avant de parler de ce super-pouvoir de Haskell, nous devons parler d’un autre aspet essentiel: les Types.

02_Hard_Part/16_Functions.lhs

Les types

Dali, the madonna of port Lligat

tl;dr:

  • type Name = AnotherType n’est qu’un alias de type, le compilateur ne fera pas la différence entre les deux.
  • data Name = NameConstructor AnotherType le compilateur fera la différence.
  • data permet de construire de nouvelles structures qui peuvent être récursives.
  • deriving est magique et créé automatiquement des fonctions pour vous.

En Haskell, les types sont forts et statiques.

Pourquoi est-ce important? Cela vous aidera a éviter beaucoup d’erreurs. En Haskell, la majorité des bugs est repérée durant la compilation de votre programme. Et la raison principale de cela est l’inférence de type durant la compilation. L’inférence de type permet de détecter plus facilement lorsque vous utilisez le mauvais paramètre au mauvais endroit, par exemple.

Inférence de type

Le typage statique est généralement essentiel pour une exécution rapide. Mais la plupart des langages typés statiquement ont du mal à généraliser des concepts. La “grâce salvatrice” de Haskell est qu’il peut inférer des types.

Voici un exemple simple, la fonction square en Haskell:

Cette fonction peut mettre au carré n’importe quel type Numeral. Vous pouvez l’utilser avec un Int, un Integer, un Float, un Fractional ou même un Complex. Preuve par l’exemple:

% ghci
GHCi, version 7.0.4:
...
Prelude> let square x = x*x
Prelude> square 2
4
Prelude> square 2.1
4.41
Prelude> -- charge le module Data.Complex
Prelude> :m Data.Complex
Prelude Data.Complex> square (2 :+ 1)
3.0 :+ 4.0

x :+ y est la notation pour le complexe (x + iy)

Comparons maintenant avec la quantité de code nécessaire pour le faire en C:

Pour chaque type, vous avez besoin d’écrire une nouvelle fonction. Le seul moyen de se débarrasser de ce problème est d’utiliser des astuces de méta-programmation, par exemple en utilisant le pré-processeur. en C++ il y a un meilleur moyen, les templates:

#include <iostream>
#include <complex>
using namespace std;

template<typename T>
T square(T x)
{
    return x*x;
}

int main() {
    // int
    int sqr_of_five = square(5);
    cout << sqr_of_five << endl;
    // double
    cout << (double)square(5.3) << endl;
    // complex
    cout << square( complex<double>(5,3) )
         << endl;
    return 0;
}

C++ fait un bien meilleur travail que C ici. Mais pour des fonctions plus complexes, la syntaxe sera difficile à suivre. Voyez cet article pour quelques exemples. (_NDT: toujours en anglais)

En C++ vous devez déclarer qu’une fonction peut marcher avec différents types. En Haskell, c’est le contraire. La fonction sera aussi générale que possible par défaut.

L’inférence de type donne à Haskell le sentiment de liberté que les langages dynamiquement typés proposent. Mais contrairement aux langages dynamiquement typés, la majorité des erreurs est détectée avant de lancer le programme. Généralement, en Haskell:

“Si ça compile, ça fait certainement ce que vous attendiez.”

02_Hard_Part/21_Types.lhs

Construction de types

Vous pouvez construire vos propres types. D’abord, vous pouvez utiliser des alias ou des synonymes de types.

02_Hard_Part/21_Types.lhs

02_Hard_Part/22_Types.lhs

Mais cela ne vous protège pas tellement. Essayez d’inverser les deux paramètres de showInfos et lancez le programme:

Le code sera compilé et exécuté. En fait vous pouvez remplace Name, Color et String n’importe où. Le compilateur les traitera comme si ils était complétement identiques.

Une autre méthode est de créer vos propres type avec le mot-clé data.

Maintenant, si vous échangez les paramètres de showInfos, le compilateur se plaint! Au seul prix d’être plus verbeux, vous écartez définitivement cette erreur potentielle.

Remarquez aussi que les constructeurs sont des fonctions :

La syntaxe de data est principalement:

Généralement on utilise le même nom pour le DatatTypeName et le DataTypeConstructor.

Exemple :

Vous pouvez également utiliser cette syntaxe :

Et de nombreux accesseurs sont définis pour vous. En outre, vous pouvez utiliser une autre ordre lorsque vous définissez des valeurs.

Exemple :

02_Hard_Part/22_Types.lhs

02_Hard_Part/23_Types.lhs

Type récursif

Nous avons déjà rencontré un type récursif : les listes. Nous pourrions re-créer les listes, avec une syntaxe plus bavarde:

Si vous voulez réellement utiliser une syntxe plus simple, utilisez un nom infixe pour les constructeurs.

Le nombre après infixr donne la priorité.

Si vous voulez pouvoir écrire (Show), lire (Read), tester l’égalité (Eq) et comparer (Ord) votre nouvelle structure, vous pouvez demander à Haskell de dériver les fonctions appropriées pour vous.

Quand vous ajoutez deriving (Show) à votre déclaration, Haskell crée une fonction show pour vous. Nous verrons bientôt comment utiliser sa propre fonction show.

Ceci donne :

0 ::: (1 ::: Nil)
0 ::: (1 ::: Nil)

02_Hard_Part/23_Types.lhs

02_Hard_Part/30_Trees.lhs

Les arbres

Magritte, l

Voici une autre exemple standard : les arbres binaires.

Créons aussi une fonctions qui transforme une liste en un arbre binaire ordonné.

Remarquez à quel point cette fonction est élégante. En français :

  • une liste vide est convertie en un arbre vide
  • une liste (x:xs) sera convertie en un arbre où :
    • La racine est x
    • Le “sous-arbre” de gauche est l’arbre créé à partir des membres de la liste xs strictement inférieurs à x
    • Le “sous-arbre” de droite est l’arbre créé à partir des membres de la liste xs strictement superieurs à x

Vous devriez obtenir :

Node 7 (Node 2 Empty (Node 4 Empty Empty)) (Node 8 Empty Empty)

C’est une représentation de notre arbre informative mais plutôt déplaisante.

02_Hard_Part/30_Trees.lhs

02_Hard_Part/31_Trees.lhs

Juste pour le plaisir, codons un meilleur affichage pour nos arbres. Je me suis simplement amusé à faire une belle fonction pour afficher les arbres de façon générale. Vous pouvez passer cette partie si vous la trouvez difficile à suivre.

Nous avons quelques changements à faire. Enlevons le deriving (Show) de la déclaration de notre type BinTree. Il serait aussi utile de faire de BinTree une instance de (Eq et Ord), nous serons ainsi capable de tester l’égalité et de comparer des arbres.

Sans le deriving (Show), Haskell ne crée pas de méthode show pour nous. Nous allons créer notre propre version. Pour accomplir cela, nous devons déclarer que notre type BinTree a est une instance de la classe de type Show. La syntaxe générale est :

Voici ma version pour afficher un arbre binaire. Ne vous inquiétez pas de sa complexité apparente. J’ai fait beaucoup d’améliorations pour afficher même les objets les plus étranges.

La méthode treeFromList reste identique.

Et maintenant, nous pouvons jouer :

Arbre binaire d'Int:
< 7
: |--2
: |  |--1
: |  `--4
: |     |--3
: |     `--6
: `--8
:    `--21
:       |--12
:       `--23

Maintenant c’est beaucoup mieux ! La racine est montrée en commençant la ligne avec le caractère <. Et chaque ligne suivante est commence par :. Mais nous pourrions aussi utiliser un autre type.

Arbre binaire de chaînes de caractères
< "foo"
: |--"bar"
: |  `--"baz"
: `--"gor"
:    `--"yog"

Commme nous pouvons tester l’égalité et ordonner des arbres, nous pouvons aussi faire des arbres d’arbres!

Arbre binaire d'arbres binaires de Char :
< < 'b'
: : |--'a'
: : `--'z'
: |--< 'b'
: |  : |--'a'
: |  : `--'r'
: `--< 'z'
:    : `--'a'
:    :    `--'r'

C’est pour cela que j’ai choisi de préfixer chaque ligne par un : (sauf pour la racine).

Yo Dawg Tree

Qui est équivalent à

et donne :

Arbre d'arbres d'arbres de Char :
< < < 'Y'
: : : `--'O'
: : `--< 'D'
: :    : |--'A'
: :    : `--'W'
: :    :    `--'G'
: |--< < 'I'
: |  : `--< 'H'
: |  :    : |--'E'
: |  :    : |  `--'A'
: |  :    : |     `--'D'
: |  :    : `--'R'
: `--< < 'Y'
:    : : `--'O'
:    : :    `--'U'
:    : `--< 'L'
:    :    : `--'I'
:    :    :    |--'E'
:    :    :    `--'K'
:    :    `--< 'T'
:    :       : `--'R'
:    :       :    |--'E'
:    :       :    `--'S'

Remarquez que les arbres en double ne sont pas insérés. Il n’y a qu’un seul arbre correspondant à "I","HEARD". Nous avons ceci presque gratuitement, car nous avons déclaré Tree comme instance de Eq.

Voyez à quel point cette structure est formidable : Nous pouvons faire des arbres contenant seulement des entiers, des chaînes de caractères, mais aussi d’autres arbres. Et nous pouvons même faire un arbre contenant un arbre d’arbres!

02_Hard_Part/31_Trees.lhs

02_Hard_Part/40_Infinites_Structures.lhs

Structures infinies

Escher

On dit souvent que Haskell est paresseux.

En fait, si vous êtes un petit peu pédant, vous devriez dire que Haskell est non-strict (NDT: En anglais, pour changer). La paresse est juste une implémentation commune aux langages non-stricts.

Alors que signifie “non-strict”? D’après le wiki de Haskell :

La réduction (terme mathématique pour “évaluation”) procède depuis l’extérieur.

Donc si vous avez (a+(b*c)), alors vous réduisez + d’abord, puis vous réduisez (b*c)

Par exemple en Haskell vous pouvez faire :

Et ça s’arrête.

Comment ?

Au lieu d’essayer d’évaluer numbers entièrement, Haskell évalue les éléments seulement lorsque c’est nécessaire.

Remarquez aussi qu’en Haskell, il y a une notation pour les listes infinies

[1..]   ⇔ [1,2,3,4...]
[1,3..] ⇔ [1,3,5,7,9,11...]

et que la majorité des fonctions fonctionnera avec ces listes. Il y a aussi une fonction take équivalente à notre take'.

02_Hard_Part/40_Infinites_Structures.lhs

02_Hard_Part/41_Infinites_Structures.lhs

This code is mostly the same as the previous one.

Supposons que nous ne nous préoccupions pas d’avoir une arbre ordonné. Voici un arbre binaire infini :

Un arbre complet où chaque noeud est égal à 0. Maintenant je vais vous prouver que nous pouvons manipuler cet arbre avec la fonction suivante :

Regardez ce qui se passe avec ce programme :

Le code compile, se lance et s’arrête en donnant ce résultat :

<  0
: |-- 0
: |  |-- 0
: |  |  |-- 0
: |  |  `-- 0
: |  `-- 0
: |     |-- 0
: |     `-- 0
: `-- 0
:    |-- 0
:    |  |-- 0
:    |  `-- 0
:    `-- 0
:       |-- 0
:       `-- 0

Pour nous chauffer encore un peu les neurones, faisons un arbre plus intéressant :

Un autre moyen de créer cet arbre est d’utiliser une fonction d’ordre supérieur. Cette fonction devrait être similaire à map n, mais devrait travailler sur un BinTree au lieu d’une liste. Voici cette fonction :

NB: Je ne parlerai pas plus de cette fonction ici. Si vous vous intéressez à la généralisation de map à d’autres structures de données, cherchez des informations sur les foncteurs et fmap.

Notre définition est maintenant :

Regardez le résultat pour

<  0
: |-- -1
: |  |-- -2
: |  |  |-- -3
: |  |  `-- -1
: |  `-- 0
: |     |-- -1
: |     `-- 1
: `-- 1
:    |-- 0
:    |  |-- -1
:    |  `-- 1
:    `-- 2
:       |-- 1
:       `-- 3

02_Hard_Part/41_Infinites_Structures.lhs

Partie de difficulté infernale

Félicitations pour être allé si loin! Maitenant, les choses vraiment extrêmes peuvent commencer.

Si vous êtes comme moi, vous êtes déjà familier avec le style fonctionnel. Vous devriez également comprendre les avantages de la paresse par défaut. Mais vous ne comprenez peut-être pas vraiment par où commencer pour faire un vrai programme. Et en particulier :

  • Comment s’occuper des effets ?
  • Pourquoi y a t-il une étrange notation impérative lorsque l’on s’occupe de l’Entrée/Sortie? (E/S, IO pour Input/Output en anglais)

Accrochez-vous, les réponses risquent d’être compliquées. Mais elles en valent la peine.

03_Hell/01_IO/01_progressive_io_example.lhs

S’occuper de l’E/S (IO)

Magritte, Carte blanche

tl;dr:

Une fonction typique qui fait de l’IO ressemble à un programme impératif:

f :: IO a
f = do
  x <- action1
  action2 x
  y <- action3
  action4 x y
  • Pour définir la valeur d’un objet on utilise <- .
  • Le type de chaque ligne est IO *; dans cet exemple:
    • action1 :: IO b
    • action2 x :: IO ()
    • action3 :: IO c
    • action4 x y :: IO a
    • x :: b, y :: c
  • Quelques objets ont le type IO a, cela devrait vous aider à choisir. En particulier vous ne pouvez pas utiliser de fonctions pures directement ici. Pour utiliser des fonctions pures vous pourriez faire action2 (pureFunction x) par exemple.

Dans cette section, je vais expliquer comment utiliser l’IO, pas comment ça marche. Vous verrez comment Haskell sépare les parties pures et impures du programme.

Ne vous arrêtez pas sur les détails de la syntaxe Les réponses viendront dans la section suivante.

Que cherchons-nous à faire?

Demander une liste de nombres à l’utilisateur. Afficher la somme de ces nombres.

Il devrait être simple de comprendre le comportement de ce programme. Analysons les types en détails.

putStrLn :: String -> IO ()
getLine  :: IO String
print    :: Show a => a -> IO ()

Ou, de manièree plus intéressante, on remarque que chaque expression dans le bloc do est de type IO a.

main = do
  putStrLn "Enter ... " :: IO ()
  getLine               :: IO String
  print Something       :: IO ()

Nous devrions aussi prêter attention à l’effet du symbole <-.

do
 x <- something

Si something :: IO a alors x :: a.

Une autre remarque importante sur l’IO: Toutes les lignes d’un bloc do doivent être d’une des deux formes suivantes :

action1             :: IO a
                    -- in this case, generally a = ()

ou

value <- action2    -- where
                    -- action2 :: IO b
                    -- value   :: b

Ces deux types de ligne correspondent à deux types différents de séquençage d’action. La signification de cette phrase devrait être plus claire à la fin de la prochaine section.

03_Hell/01_IO/01_progressive_io_example.lhs

03_Hell/01_IO/02_progressive_io_example.lhs

Maintenant voyons comment ce programme se comporte. Par exemple, que ce passe-t-il si l’utilisateur entre une mauvaise valeur? Essayons :

    % runghc 02_progressive_io_example.lhs
    Enter a list of numbers (separated by comma):
    foo
    Prelude.read: no parse

Argh! Un message d’erreur effrayant et un crash ! Notre première amélioration sera de répondre avec un message plus amical.

Pour faire cela, nous devons détecter que quelque chose s’est mal passé. Voici un moyen de le faire : utiliser le type Maybe. C’est un type très utilisé en Haskell.

Mais qu’est-ce que c’est ? Maybe est un type qui prend un paramètre. Sa définition est :

C’est un bon moyen de dire qu’il y a eu une erreur en essayant de créer/évaluer une valeur. La fonction maybeRead en est un bon exemple. C’est une fonction similaire à read3, mais s’il y a un problème, la valeur retournée est Nothing. Si la valeur est bonne, la valeur retournée est Just <la valeur>. Ne vous efforcez pas trop de comprendre cette fonction. J’utilise une fonction de plus bas niveau que read : reads.

Maintenant, pour être plus lisible, on définit une fonction comme ceci : Si la chaîne a un mauvais format, elle retournera Nothing. Sinon, par exemple pour “1,2,3”, cela retournera Just [1,2,3].

Nous avons juste à tester la valeur dans notre fonction principale.

En cas d’erreur, on affiche un joli message.

Notez que le type de chaque expression dans le bloc do de main reste de la forme IO a. La seule construction étrange est error. Disons juste que error msg prend le type nécessaire (ici, IO ()).

Une chose très importante à noter est le type de toutes les fonctions définies jusqu’ici. Il n’y a qu’une seule fonction qui contient IO dans son type : main. Cela signifie que main est impure. Mais main utilise getListFromString, qui, elle, est pure. Nous pouvons donc facilement repérer quelles fonctions sont pures et lesquelles sont impures, seulement en regardant leur type.

Pourquoi la pureté a-t-elle de l’importance? Parmi ses nombreux avantages, en voici trois :

  • Il est beaucoup plus facile de penser à du code pur qu’à du code impur.
  • La pureté vous protège de tous les bugs difficiles à reproduire dûs aux effets de bord.
  • Vous pouvez évaluer des fonctions pures dans n’importe quel ordre ou en parallèle, sans prendre de risques.

C’est pourquoi vous devriez mettre le plus de code possible dans des fonctions pures.

03_Hell/01_IO/02_progressive_io_example.lhs

03_Hell/01_IO/03_progressive_io_example.lhs

La prochaine étape sera de demander la liste de nombres à l’utilisateur encore et encore jusqu’à ce qu’il entre une réponse valide.

Nous gardons la première partie :

Maintenant nous créons la fonction qui demandera une liste d’entiers à l’utilisateur jusqu’à ce que l’entrée soit correcte

Cette fonction est de type IO [Integer]. Cela signifie que la valeur récupérée est de type [Integer] et est le résultat d’actions d’E/S. D’aucuns diront avec enthousiasme :

«C’est un [Integer] dans un IO !»

Si vous voulez comprendre les détails derrière tout cela, vous devrez lire la prochaine section. Mais si vous voulez seulement utiliser l’E/S, contentez-vous pratiquer un peu et rappelez-vous de penser aux types.

Finalement, notre fonction mainest bien plus simple :

Nous avons fini notre introduction à l’IO. C’était plutôt rapide. Voici les principales choses à retenir :

  • Dans le bloc do, chaque expression doit avoir le type IO a. Vous êtes donc limité quant au panel d’expression disponibles. Par exemple, getLine, print, putStrLn, etc…
  • Essayez d’externaliser le plus possible les fonctions pures.
  • le type IO a signifie : une action d’E/S qui retourne un élément de type a. L’IO représente des actions; sous le capot, IO a est le type d’une fonction. Lisez la prochaine section si vous êtes curieux.

Si vous pratiquez un peu, vous devriez être capable d’utiliser l’IO.

-Exercices_:

  • Écrivez un programme qui additionne tous ses arguments. Utilisez la fonction getArgs.

03_Hell/01_IO/03_progressive_io_example.lhs

Le truc des IO révélé

Magritte, ceci n

Voici un tlpl: pour cette section.

Pour séparer les parties pures et impures, main est définie comme une fonction. qui modifie l’état du monde.

main :: World -> World

Une fonction aura des effets de bord si elle a ce type. Mais regardez cette fonction main typique:


main w0 =
    let (v1,w1) = action1 w0 in
    let (v2,w2) = action2 v1 w1 in
    let (v3,w3) = action3 v2 w2 in
    action4 v3 w3

Nous avons beaucoup d’élements temporaires (ici, w1, w2 et w3) qui doivent être passés à l’action suivante.

Nous créons une fonction bind ou (>>=). Avec bind nous n’avons plus besoin de noms temporaires.

main =
  action1 >>= action2 >>= action3 >>= action4

Bonus: Haskell a du sucre syntaxique :

main = do
  v1 <- action1
  v2 <- action2 v1
  v3 <- action3 v2
  action4 v3

Pourquoi avons-nous utilisé cette syntaxe étrange, et quel est exactement le type IO? Cela peut sembler un peu magique.

Pour l’instant, oublions les parties pures de notre programme, et concentrons-nous sur les parties impures:

Première remarque : on dirait de l’impératif. Haskell est assez puissant pour faire sembler impératif du code impur. Par exemple, si vous le vouliez vous pourriez créer une boucle while en Haskell. En fait, pour utiliser les IO, le style impératif est en général plus approprié.

Mais vous devriez avoir remarqué que la notation est inhabituelle. Voici pourquoi, en détail.

Dans un langage impur, l’état du monde peut être vu comme une énorme variable globale cachée. Cette variable cachée est accessible par toutes les fonctions du langage. Par exemple, vous pouvez lire et écrire dans un fichier avec n’importe quelle fonction. Le fait que le fichier putatif existe ou non est une éventualité qui relève des états possibles que le monde courant peut prendre.

En Haskell l’état courant du monde n’est pas caché. Au contraire, il est dit explicitement que main est une fonction qui change potentiellement l’état du monde. Son type est donc quelque chose comme :

Les fonctions ne sont pas toutes susceptibles de modifier cette variable. Celle qui peuvent la modifier sont impures. Les fonctions qui ne peuvent pas agir sur la variable sont pures4.

Haskell considère l’état du monde comme une variable à passer à main. Mais son type réel est plus proche de celui ci5 :

Le type () est le type “unit”. Rien à voir ici.

Maintenant réécrivons notre fonction main avec cela à l’esprit :

D’abord, on remarque que toutes les fonctions avec des effets de bord doivent avoir le type :

où a est le type du résultat. Par exemple, une fonction getChar aura le type `World -> (Char, World).

Une autre chose à noter est l’astuce pour corriger l’ordre d’évaluation. En Haskell, pour évaluer f a b, vous avez l’embarras du choix :

  • évaluer d’abord a puis b puis f a b
  • évaluer d’abord b puis a puis f a b
  • évaluer a et b parallèlement, puis f a b

Cela vient du fait que nous avons recours à une partie pure du langage.

Maintenant, si vous regardez la fonction main, vous voyez tout de suite qu’il faut évaluer la première ligne avant la seconde, car pour évaluer la seconde ligne vous devez utliser un paramètre donné suite à l’évaluation de la première ligne.

Cette astuce fonctionne très bien. Le compilateur donnera à chaque étape un pointeur sur l’id du nouveau monde courant. En réalité, print sera évaluée comme suit :

  • Écrit quelque chose sur l’écran
  • Modifie l’id du monde
  • renvoyer ((), id du nouveau monde).

Maintenant, si jetez un oeil au style de la fonction main, vous remarquerez qu’il est clairement peu commode. Essayons de faire la même chose avec la fonction askUser :

Avant :

Après :

C’est similaire, mais peu commode. Voyez-vous toutes ces variables temporaires w?.

Voici la leçon : une implémentation naïve des IO dans les langages fonctionnels purs serait maladroite !

Heureusement, il y a un meilleur moyen de résoudre ce problème. Nous voyons un motif. Chaque ligne est de la forme :

Même si pour certaines lignes l’argument x n’est pas nécessaire. La sortie est un couple, (answer, newWorldValue). Chaque fonction f doit avoir un type similaire à :

Et ce n’est pas fini, nous pouvons aussi remarquer que nous suivons toujours le même motif :

Chaque action peut prendre de 0 à n paramètres. Et en particulier, chaque action prend comme paramètre le résultat de la ligne précédente.

Par exemple, nous pourrions aussi avoir :

Avec, bien entendu, actionN w :: (World) -> (a,World).

IMPORTANT: Il y a seulement 2 schémas importants à considérer :

let (x,w1) = action1 w0 in
let (y,w2) = action2 x w1 in

et

let (_,w1) = action1 w0 in
let (y,w2) = action2 w1 in
Jocker pencil trick

Maintenant, préparez-vous pour un petit tour de magie ! Faisons disparaître les variables temporaires de monde courant. Nous allons attacher (NDT: bind en anglais) les deux lignes. Définissons la fonction bind. Son type est assez intimidant au début :

Mais gardez en tête que (World -> (a,World)) est le type d’une action d’IO. Renommons-le pour plus de clarté :

Quelques exemples de fonctions :

getLine est une action d’E/S qui prend le monde en paramètre et retourne un couple (String, World). Cela peut être résumé par : getLine est de type IO String, que nous pouvons voir comme une action d’E/S qui retournera une chaîne de caractères “dans une E/S”.

La fonction print est elle aussi intéressante. Elle prend un argument qui peut être montré avec show. En fait, elle prend deux arguments. Le premier est la valeur et le deuxième est l’état du monde. Elle retourne un couple de type ((), World). Cela signifie qu’elle change l’état du monde, mais ne produit pas d’autre donnée.

Ce nouveau type IO a nous aide à simplifier le type de bind :

Cela dit que bind prend deux actions d’E/S en paramètres et retourne une autre action d’E/S.

Maintenant, rappelez-vous des motifs importants. Le premier était :

Voyez les types :

Cela ne vous semble-t-il pas familier ?

L’idée est de cacher l’argument World avec cette fonction. Allons-y ! Par exemple si nous avions voulu simuler :

Maintenant, en utilisant la fonction bind :

Comme print est de type Show a => a -> (World -> ((), World)), nous savons que res = () (type unit) Si vous ne voyez pas ce qui est magique ici, essayons avec trois lignes cette fois.

Qui est équivalent à :

Avez-vous remarqué quelque chose ? Oui, aucune variable World temporaire n’est utilisée ! C’est MA._GIQUE_.

Nous pouvons utiliser une meilleure notation. Utilisons (>>=) au lieu de bind. (>>=) est une fonction infixe, comme (+); pour mémoire : 3 + 4 ⇔ (+) 3 4

Ho Ho Ho! Joyeux Noël ! fr; Haskell a confectionné du sucre syntaxique pour vous :

Est remplacé par :

Remarquez que vous pouvez utliser x dans action2 et x et y dans action3.

Mais que se passe-t-il pour les lignes qui n’utilisent pas le <- ? Facile, une autre fonction blindBind :

Je n’ai pas simplifié cette définition pour plus de clarté. Bien sûr, nous pouvons utiliser une meilleure notation avec l’opérateur (>>).

Et

Devient

Enfin, une autre fonction est plutôt utile.

D’une manière générale, c’est une façon de mettre des valeurs pures dans le “contexte d’E/S”. Le nom général pour putInIO est return. C’est un plutôt un mauvais nom lorsque vous commencez à programmer en Haskell. return est très différent de ce à quoi vous pourriez être habitué.

03_Hell/01_IO/21_Detailled_IO.lhs

Pour finir, traduisons notre exemple :

Se traduit en :

Vous pouvez compiler ce code pour vérifier qu’il marche.

Imaginez à quoi il ressemblerait sans le (>>) et (>>=).

03_Hell/01_IO/21_Detailled_IO.lhs

03_Hell/02_Monads/10_Monads.lhs

Les monades

Dali, reve. It represents a weapon out of the mouth of a tiger, itself out of the mouth of another tiger, itself out of the mouth of a fish itself out of a grenade. I could have choosen a picture of the Human centipede as it is a very good representation of what a monad really is. But just to think about it, I find this disgusting and that wasn

Maintenant le secret peut être dévoilé : IO est une monade. Être une monade signifie que vous avez accès à du sucre syntaxique avec la notation do. Mais principalement, vous avez accès à un motif de codage qui tempérera le flux de votre code.

Remarques importantes :

  • Le monades n’ont pas forcément quoi que ce soit à voir avec les effets de bord ! Il y a beaucoup de monades pures.
  • Les monades concernent plus le séquençage.

En Haskell, Monad est une classe de type. Pour être une instance d’une classe de type, vous devez fournir les fonctions (>>=) et return. La fonction (>>) est dérivée de (>>=). Voici commment la classe de type Monad est déclarée (grosso modo) :

Remarques :

  • le mot-clé class n’est pas votre ami. Une classe en Haskell n’est pas du même genre que celle des langages orientés-objet. Elles ont beaucoup de similarités avec les interfaces de Java. Un meilleur mot aurait été typeClass, ce qui signifierait un ensemble de types. Pour qu’un type appartienne à une classe, toutes les fonctions de cette classe doivent être fournies pour ce type.
  • Dans cet exemple particulier de classe de type, le type m doit être un type qui prend un argument. par exemple IO a, mais aussi Maybe a, [a], etc…
  • Pour être une monade utile, votre fonction doit obéir à quelques règles. Si votre construction n’obéit pas à ces règles, des choses étranges pourraient se produire :
return a >>= k  ==  k a
m >>= return  ==  m
m >>= (\x -> k x >>= h)  ==  (m >>= k) >>= h

Maybe est une monade

Il y a beaucoup de types différents qui sont des instances de Monad. L’un des plus faciles à décrire est Maybe. Si vous avez une séquence de valeurs Maybe, vous pouvez utiliser les monades pour les manipuler. C’est particulièrement utile pour enlever des constructions if..then..else.. trop nombreuses.

Imaginez une opération bancaire complexe. Vous êtes éligible pour gagner 700€ seulement si vous pouvez effectuer une liste d’opérations sans tomber en dessous de zéro.

03_Hell/02_Monads/10_Monads.lhs

03_Hell/02_Monads/11_Monads.lhs

Maintenant, améliorons cela en utilisant le fait que Maybe est une Monade.

03_Hell/02_Monads/11_Monads.lhs

03_Hell/02_Monads/12_Monads.lhs

Pas mauvais, mais nous pouvons faire encore mieux :

Nous avons prouvé que les monades sont un bon moyen de rendre notre code plus élégant. Remarquez que cette idée d’organisation de code, en particulier pour Maybe, peut être utilisée dans la plupart des langages impératifs. En fait, c’est le type de construction que nous faisons naturellement.

Une remarque importante :

Le premier élement de la séquence qui sera évalué comme Nothing stoppera l’évaluation. Cela signifie que vous n’exécutez pas toutes les lignes. Cela découle du caractère paresseux de Haskell.

Vous pourriez aussi revoir ces exemples avec la définition de (>>=) pour Maybe en tête :

La monade Maybe a prouvé par un simple exemple qu’elle est utile. Nous avons vu l’utilité de la monade IO. Mais maintenant, voici un exemple encore plus cool : les listes.

03_Hell/02_Monads/12_Monads.lhs

03_Hell/02_Monads/13_Monads.lhs

La monade List

Golconde de Magritte

La monade List nous aide à simuler des calculs non-déterministes. C’est parti :

Ma. GIQUE. :

[(1,1,7),(1,1,8),(1,1,9),(1,1,10),(1,2,9),(1,2,10)]

Pour la monade List, il y a aussi un sucre syntaxique :

Je ne listerai pas toutes les monades, car il y en a beaucoup. Utiliser les monades simplifie la manipulations de plusieurs notions dans les langages purs. Les monades sont très utiles, en particulier pour :

  • L’E/S (IO),
  • les calculs non-déterministes,
  • générer des nombres pseudo-aléatoires,
  • garder un état de configuration,
  • écrire un état,
  • …

Si vous m’avez suivi jusqu’ici, alors vous avez terminé ! Vous connaissez les monades6 !

03_Hell/02_Monads/13_Monads.lhs

Appendice

Cette section n’est pas vraiment sur l’apprentissage d’Haskell. Elle est ici pour discuter de quelques détails.

04_Appendice/01_More_on_infinite_trees/10_Infinite_Trees.lhs

Revenons sur les arbres infinis

Dans la section sur les structures infinies nous avons vu quelques constructions simples. Malheureusement, nous avons enlevé deux propriétés de notre arbre:

  1. Pas de valeurs identiques
  2. Arbre bien ordonné

Dans cette section nous allons tenter de garder la première propriété. Concernant la seconde, nous ne devons pas nous en préoccuper ici mais nous discuterons de comment la garder le plus possible.

This code is mostly the same as the one in the tree section.

Notre première étape est de créer une liste de nombres pseudo-aléatoires:

Pour mémoire, voici la définition de treeFromList

et treeTakeDepth:

Voyez le résultats de:

% runghc 02_Hard_Part/41_Infinites_Structures.lhs
take 10 shuffle
[3123,1915,707,3830,2622,1414,206,3329,2121,913]
treeTakeDepth 4 (treeFromList shuffle)

< 3123
: |--1915
: |  |--707
: |  |  |--206
: |  |  `--1414
: |  `--2622
: |     |--2121
: |     `--2828
: `--3830
:    |--3329
:    |  |--3240
:    |  `--3535
:    `--4036
:       |--3947
:       `--4242

Le code fonctionne! Attention cependant, cela marchere seulement si vous avez toujours quelque chose à mettre dans une branche.

Par exemple

tournera en boucle pour toujours. Simplement parce que le code essayera d’accéder à première valeur de filter (<1) [2..]. Mais filter n’est pas assez intelligent pour comprendre que le résultat est une liste vide.

Toutefois, cela reste un exemple sympa de ce qu’un programme non-stricit a à offrir.

Laissé pour exercice au lecteur:

  • Prouver l’existence d’un nombre n tel que treeTakeDepth n (treeFromList shuffle) provoquera une boucle infinie.
  • Trouver une borne supérieur n.
  • Prouver qu’il n(y a pas de liste shuffle qui termine le programme pour n’importe quelle profondeur.

04_Appendice/01_More_on_infinite_trees/10_Infinite_Trees.lhs

04_Appendice/01_More_on_infinite_trees/11_Infinite_Trees.lhs

This code is mostly the same as the preceding one.

Pour résoudre ces problèmes nous allons modifier légèrement nos fonctions treeFromList et shuffle.

Un premier problème est le manque de nombres différents dans notre immlémentation de shuffle. Nous avons généré seulement 4331 nombres différents. Pour résoudre cela nous allons faire un meilleure fonction shuffle.

Cette fonction à la propriété de ne pas avoir de bornes supérieure ou inférieure. Mais avoir une meilleure list shuffle n’est pas assez pour entrer dans une boucle infinie.

Généralement, nous ne pouvons pas décider que filter (<x) xs est vide. Donc pour résoudre le problème, je vais autoriser quelques erreurs dans la création de notre arbre binaire. Cette nouvelle version du code peut créer des arbres binaires qui n’ont pas à suivre les propriétés suivantes pour quelque uns de leurs noeuds:

Tous les élements de la branche de gauche doit être strictement inférieur au la valeur racine.

Remarquez que cela donnera souvent un arbre ordonné. En outre, avec cette construction, chaque noeud est unique dans l’arbre.

Voici notre nouvelle version de treeFromList. Nous avons simplement remplacé filter par safefilter.

Cette nouvelle fonction safefilter est presque équivalente à filter mais n’entre pas dans des boucles infinies si le résultat est une liste finie. Si elle ne peut pas trouver un élément pour lequel le test est vrai après 10000 étapes consécutives, alors elle considère que la recherche est finie.

Maintenant faites tourner le programme et soyez heureux:

Vous devriez réaliser que le temps nécessaire pour afficher chaque valeur est différent. C’est parce que Haskell calcule chaque valeur lorsqu’il en a besoin. Et dans ce cas, il est demandé de l’afficher à l’écran.

Vous pouvez même essayer de remplacer la profondeur de 8 par 100. Cela marchera sans tuer votre RAM! La gestion de la mémoire est faite naturellement par Haskell.

Laissé comme exercices au lecteur:

  • Même avec une grande valeur constante pour deep et nbTry, cela semble marcher correctement. Mais dans le pire des cas, cela peut devenir exponentiel. Créez la pire liste à donner comme paramètre à treeFromList. indice: pensez à ([0,-1,-1,....,-1,1,-1,...,-1,1,...]).
  • J’ai commencé à implémenter safefilter comme ceci: 
    safefilter' f l = if filter f (take 10000 l) == []
                  then []
                  else filter f l
    Expliquer pourquoi cela ne fonctionne pas et peut entrer dans une boucle infinie.
  • Supposez que shuffle est une liste de nombre réellement aléatoires avec de plus en plus de bornes. Si vous étudiez un peu cette structure, vous découvrirez qu’elle a toutes les chances d’être finie. En utilisant le code suivant (supposez que nous pouvons utliser safefilter' directement comme si cela n’était pas dans le where de safefilter. trouvez une définition de f telle que, avec une probabilité de 1, treeFromList' shuffle est infinie?. Et prouvez-le. Avertissement, ce n’est qu’une conjecture.

04_Appendice/01_More_on_infinite_trees/11_Infinite_Trees.lhs

Remerciements

Merci à /r/haskell et /r/programming. Vos commentaires étaient plus que bienvenus.

Particulièrement, je voudrais remercier mille fois Emm pour le temps qu’il a consacré à corriger mon anglais. Merci beaucoup.

  1. Même si tous les langages récents essayent de les cacher, ils restent présents.↩

  2. Je sais que je triche. Mais je parlerais de la non-rigueur plus tard. ↩

  3. Qui est elle-même très similaire à la fonction eval de javascript, appliquée sur une chaîne contenant du code au format JSON.↩

  4. Il y a quelques exceptions peu sûres à cette règle. Mais vous ne devriez pas en voir en application réelle, sauf pour le debugging.↩

  5. Pour les curieux, le vrai type est data IO a = IO {unIO :: State# RealWorld -> (# State# RealWorld, a #)}. Tous les # ont rapport avec l’optimisation et j’ai échangé quelques champs dans mon exemple. Mais c’est l’idée de base.↩

  6. Vous aurez quand même besoin de pratiquer un peu pour vous habituer à elles et pour comprendre quand les utiliser et créer les vôtres. Mais vous avez déjà fait un grand pas dans cette direction.↩