Introduction à Haskell

.gitignore

\#*\#
.*

anonyme.hs

Prelude> map (\ x -> 2 * x) [1 .. 5]
[2,4,6,8,10]

comprehension.hs

Prelude> [ x * 10 | x <- [1..10], odd x ]
[10,30,50,70,90]

courteIntroductionHaskell.html

<p>J'ai entendu parler d'Haskell pour la première fois à l'université. J'entendais que c'était un langage très élégant, amusant et bien plus avancé qu'OCaml. Mais OCaml me donnait déjà bien du mal, et c'était ce dernier qui était demandé pour les examens et les projets de programmation. Je n'étais donc pas prêt à apprendre Haskell à ce moment.</p>
<p>Plus tard, par curiosité, j'ai regardé quelques projets écrits en Haskell. Je suis alors tombé sur <a href="http://xmonad.org/">xmonad</a>, un gestionnaire de fenêtres spartiate, mais avec des idées intéressantes, comme l'agencement automatique. J'ai aussi découvert la bibliothèque <a href="http://legacy.cs.uu.nl/daan/download/parsec/parsec.html">Parsec</a>, qui permet d'écrire des parseurs très simplement, et dont la lecture du code m'a convaincu que la notion de fonction était une abstraction vraiment puissante.</p>
<p>Lors de mon premier contact avec du code Haskell, je n'ai pas été très enthousiaste :
<ul>
  <li>Cela ne ressemblait à aucun langage que je connaisse, on aurait dit une peu de l'anglais mathématique.</li>
  <li>Après quelques tentatives de modification du code, je me faisais insulter par le compilateur...</li>
</ul>
<p> Mais ma curiosité était piquée. J'ai toujours été intrigué par les langages que je ne comprends pas. De plus, il y avait une promesse de concision, vu qu'il me semblait que l'on puisse faire beaucoup avec peu de lignes.
</p>
<h2>Qu'est-ce que Haskell ?</h2>
<p> Haskell est d'abord un langage de comité, composé de mathématiciens et d'informaticiens désireux de faire des expériences en programmation fonctionnelle, et aussi de créer un langage utilisable pour écrire des applications. Le langage étant en quelque sorte expérimental, il est en perpétuelle évolution. Impossible donc d'écrire une documentation ou un livre sans être instantanément démodé. Haskell est donc stabilisé en 1998 en tant que Haskell 98. Ce qui met fin également au comité, mais pas à la vie du langage, bien au contraire. 
</p>

Quelques traits caractéristiques du langage :
<ul>
  <li>Fonctionnel : l'abstraction de base est la fonction.</li>
  <li>Pur : pas d'effets de bord.</li>
  <li>Paresseux (<em>lazy</em>) : l'évaluation se fait lorsque l'on a besoin d'une valeur, à la différence de la plupart des autres langages, où les arguments d'une fonction sont évalués avant l'appel de celle-ci. Ceci permet par exemple de manipuler des structures de données de taille infinie.</li>
</ul>

<p> Ces caractéristiques en font un langage singulier, pas forcément facile à appréhender. Le coté fonctionnel pur en font un langage de choix pour la programmation parallèle, bien qu'il n'ai pas été conçu pour cela au départ. Certaines start-up choisissent également ce langage en misant sur un avantage décisif par rapport à la concurrence. Ainsi, <a href="http://www.tsurucapital.com/en/">Tsurucapital</a> annonce sur sa page d'accueil:
<cite>
We use the Haskell programming language almost exclusively since we believe it gives the best combination of high-level cleanliness, execution safety and high performance. 
</cite>
Haskell est bien entendu aussi utilisé par des mathématiciens, mais excelle dans des taches plus communes, comme l'écriture de DSL, ou plus récemment dans la programmation web (<a href="http://www.yesodweb.com/">Yesod</a>, <a href="http://snapframework.com/">Snap</a>)
</p>

<h2>Environnement de développement</h2>
J'utilise <a href="http://www.haskell.org/ghc/"><code>ghc</code></a>, le compilateur Haskell le plus utilisé et les plus avancé à l'heure actuelle. Ghci est livré avec <code>ghci</code>, un interpréteur Haskell bâti autour de ghc. Il existe très certainement un package pour votre OS.

Si vous le souhaitez, vous pouvez essayer d'autres environnements:
<ul>
  <li><a href="http://hackage.haskell.org/platform/">Haskell Platform</a> qui est constitué de ghc et d'un ensemble de bibliothèques d'usage fréquent</li>
  <li><a href="http://www.haskell.org/hugs/">Hugs</a> est un environnement qui est aussi populaire dans le monde des débutants en Haskell.</li>
</ul>
Après avoir installé ghc (ou Haskell Platform), vous pourrez exécuter un fichier en utilisant la commande <code>runhaskell</code>, ou bien le charger dans d'interpréteur en utilisant la commande <code>ghci</code>.

Une fois dans l'interpréteur, le <em>Prelude</em> (ensemble des bibliothèques de base) est chargé et vous vous retrouvez en mode interactif.
<h2>Fonctions</h2>
En Haskell, une fonction prend en entrée des valeurs, et retourne une
valeur (qui peut bien entendu être une fonction). Une fonction ne peut pas provoquer d'effets de bord. Par conséquent, le résultat d'une fonction ne dépend que de ses paramètres. En d'autres termes, la notion d'état n'existe pas. La déclaration d'une fonction consiste en une <em>équation</em>, signifiant que la partie à gauche du signe <code>=</code> est équivalent à la partie droite.

La commande <code>:t</code> vous sera certainement utile dans l’interpréteur. Elle permet d'afficher le type d'une expression. Par exemple, si je veux connaître le type de la fonction <code>length</code> :
<script src="https://gist.github.com/1388622.js?file=type-length.hs"></script>
Cela se lit comme suit: "Quel que soit le type a, la fonction length prend en argument une liste de a, et retourne un entier".
<h2>Transformer les éléments d'une liste</h2>
Une opération très fréquente lorsque l'on programme est de parcourir une liste en appliquant une fonction à chacun de ses éléments. C'est ce que permet la fonction <code>map</code>.
<script src="https://gist.github.com/1388622.js?file=map.hs"></script>
La description du type nous montre que les arguments sont :
<ol>
  <li>Une fonction qui, pour toute valeur de type a, retourne une valeur de type b</li>
  <li>Une liste de valeurs de type a</li>
</ol>
La valeur de retour est une liste de valeurs de type b.

Dans notre exemple où l'on multiplie par deux les éléments d'une liste d'entiers, les types a et b se trouvent être égaux.
<h2>Filtrer une liste</h2>
Un autre traitement très fréquent en programmation est de filtrer les éléments d'une liste selon un prédicat. C'est ce que propose la fonction <code>filter</code>.
<script src="https://gist.github.com/1388622.js?file=filter.hs"></script>
La lecture du type nous informe que les arguments sont :
<ol>
  <li>Un prédicat, c'est à dire une fonction à un argument qui retourne un booléen</li>
  <li>Une liste d'éléments</li>
</ol>
On constate aussi que les éléments de la liste résultat sont de même types que les éléments de la liste en paramètre. Ce qui est conforme à ce que nous attendons : la liste est simplement filtrée, les valeurs ne sont pas transformées.
<h2>Fonctions anonymes</h2>
Il est possible de déclarer une fonction sans nom. Par exemple, pour une fonction qui double la valeur de son argument, on  peut écrire <code>\ x -> 2 * x</code>.  Ce qui est pratique lorsque l'on a besoin d'une fonction, mais que l'on ne veut pas prendre la peine de la définir, parce qu'elle est très petite ou triviale.
<script src="https://gist.github.com/1388622.js?file=anonyme.hs"></script>
A ceux qui se poseraient la question, le caractère <code>\</code> a été choisi pour la définition de fonctions anonymes car il ressemble (un peu) au caractère λ.
<h2 id="style-sans-point-pointless">Style "sans point" (<em>pointless</em>)</h2>
La fonction <code>(.)</code> permet de composer deux fonctions. Il faut lire le point comme le "rond" en mathématiques. Ainsi <code>f(g x)</code> est équivalent à <code>(f . g) x</code>.
De plus, une fonction s’écrivant <code>h x = (f . g) x</code> peut aussi s'écrire "sans point" <code>h = f . g</code>
Une source de confusion (et aussi de blagues) vient du terme <em>pointless</em>. Pourquoi appelle-t-on ce style "sans point", alors que justement on utilise le point ? En réalité, dans cette expression, le point ne fait pas référence au caractère, mais à l’argument d'une fonction (en anglais mathématique, on appelle cela le point). Et effectivement, dans une expression <em>pointless</em>, on n'écrit pas les arguments d'une fonction lorsqu'on la définit.
<h2 id="compréhension-de-liste-list-comprehension">Compréhension de liste (<em>list comprehension</em>)</h2>
Les compréhensions de liste sont déjà connues des développeurs Python ou Erlang. Les programmeurs Scala pourront aussi trouver des similarités avec le <code>for</code> de ce langage.

La compréhension de liste permet de transformer et de filtrer des listes dans une même expression. On peut le voir comme une combinaison de <code>filter</code> et de <code>map</code>.

La syntaxe est très inspirée de la notation de définition des ensembles en mathématiques. Par exemple, nous définissons ici la "liste des élément x multipliés par 10, pour tout x dans la liste des entiers de 1 à 10 tels que x est impair":
<script src="https://gist.github.com/1388622.js?file=comprehension.hs"></script>
Les compréhensions de liste sont un élément syntaxique très intéressant pour l'expressivité et la clarté du code.
<h2>Pour aller plus loin</h2>
<ul>
  <li><a href="http://book.realworldhaskell.org/read/">Real world Haskell</a>, un livre en ligne assez didactique.</li>
  <li><a href="http://en.wikibooks.org/wiki/Haskell">Le wiki book Haskell</a>, une bonne référence pour apprendre.</li>
  <li><a href="http://learnyouahaskell.com/chapters">Learn You a Haskell for Great Good!</a>, très progressif, mais un peu trop verbeux à mon avis.</li>
</ul>

Si vous avez aprécié cet article, sachez que d'autres sont en préparation. Nous aborderons la déclaration des type de données afin de modéliser une version simplifiée de réseau social, ainsi que d'autre manière de manipuler les listes.

filter.hs

Prelude> :t filter
filter :: (a -> Bool) -> [a] -> [a]
Prelude> filter odd [1..10]
[1,3,5,7,9]

haskellTwiter.html

<h2>Introduction</h2>
<p>Lors du <a href="http://www.barreverte.fr/une-courte-introduction-haskell">précédent article</a> nous avons quelques fonctions pour manipuler des liste. Je vous propose ici de voir comment déclarer et utiliser des type de données personnalisés afin de modéliser les relations entre les utilisateur d'un réseau social.</p>

<h2>Déclaration des types</h2>
<p>Afin de modéliser notre réseau social, nous pourrions utiliser les types de base du langage, c'est à dire représenter les relations avec une liste de tuple. Mais Haskell est un langage à typage statique, le compilateur peut donc nous aider si nous définissons des types correspondant à notre problème. Ceci rends le code bien plus lisible, et Les message du compilateur sont beaucoup plus explicites.</p>

<p>Voici comment déclarer un type représentant une personne, ne portant comme information qu'une chaine de caractères, qui est le nom de cette personne:
</p>

<pre lang="haskell">data Person = Person String deriving (Show, Eq) </pre>

<p><strong>Remarque</strong>: <code>Show</code> et <code>Eq</code> permettent respectivement d'afficher et de tester l'égalité sur des valeurs du type défini.</p>

<p>De la même manière, nous pouvons exprimer le fait qu'une personne en suit une autre en définissant un type <code>Follows</code>, portant deux valeurs de type <code>Person</code> : la personne suivie, et la personne qui suit celle-ci.</p>

<pre lang="haskell">data Follows = Follows Person Person </pre>

<p><code>Follows</code> est une relation entre deux personnes. C'est la liste de ces relations qui décrira notre réseau social</p>

<p>Definissons d'abord quelques personnes :</p>

<pre lang="haskell">jb = Person &quot;JB&quot;
  david = Person &quot;David&quot;
  jp = Person &quot;JP&quot;
  bruno = Person &quot;Bruno&quot;
</pre>

<p> <code>Person</code> est appellé <em>constructeur</em>, c'est une fonction qui permet de créer de nouvelles valeurs de type <code>Person</code>.</p>

<p>Notre réseau social est représenté simplement par une liste de relations <code>Follows</code>:</p>

<pre lang="haskell">twitter = [
  jb `Follows` david,
  jp `Follows` bruno,
  jp `Follows` jb,
  jb `Follows` jp,
  bruno `Follows` jp
  ]
</pre>

<p><strong>Remarque</strong>: Toute fonction binaire peut être utilisée de manière infixe, en utilisant les backquotes. <code>Follows a b</code> est donc stictement équivalent à <code>a `Follows` b</code> .</p>

<h2>Accéder aux données</h2>
<p>Nous allons définir deux fonctions qui permettent d'accéder aux valeurs <code>Person</code> portées par la relation <code>Follows</code>:</p>

<ul>
  <li>la personne qui suit (<code>follower</code>)</li>
  <li>la personne suivie (<code>followee</code>)</li>
</ul>

<p>Ces deux fonctions prennent en paramètre une valeur de type <code>Follows</code> et retournent une valeur de type <code>Person</code>. C'est ce qu'exprime la première ligne de chacune des définitions de fonctions suivantes. Notez que cette ligne n'est pas nécéssaire à la compilation, le compilateur sachant inférer automatiquement les types des fonctions. L'usage est cependant de présicer le type lors de la déclation d'une fonction, d'abord à des fins de documentation, mais surtout afin que les éventuelles erreurs de typage soit plus simples à comprendre. En effet le compilateur Haskell infère pour une fonction le type le plus général possible, ce qui peut parfois donner lieux à des messages troublants en cas d'erreur.</p>

<pre lang="haskell">follower :: Follows -&gt; Person
  follower (Follows a _) = a

  followee :: Follows -&gt; Person 
  followee (Follows _ b) = b
</pre>

<p>Nous utilisons ici le <em>pattern matching</em> sur le type <code>Follows</code> pour en extraire la personne qui suit, et la personne suivie.</p>

<p><strong>Remarque</strong>: L'utilisation de <em>records</em> permet au compilateur d'inférer ces fonctions d'accès au données. Les records Haskell ne sont en fait que du sucre syntaxique pour déclarer un type et ses fonctions d'accès.</p>

<h2>Trouver les suiveurs d'une personne</h2>
En utilisant la définiton précédente de notre réseau social, une question que l'on peut se poser est "pour une personne donnée, qui suit cette personne?".

<pre lang="haskell">followers' ::  Person -&gt; [Follows] -&gt; [Person]
  followers person twitter = map follower $ filter (\follows -> followee follows == person) twitter
</pre>


<h3>Style &quot;sans point&quot; (<em>point free</em>)</h3>
<pre lang="haskell">followers' ::  Person -&gt; [Follows] -&gt; [Person]
  followers' p = map follower . filter ((p == ) . followee) 
</pre>

<h3>Compréhension de liste (<em>list comprehension</em>)</h3>
<pre lang="haskell">followers'' ::  Person -&gt; [Follows] -&gt; [Person]
  followers'' p twitter = [a | Follows a b &lt;- twitter, b == p]

  followers''' ::  Person -&gt; [Follows] -&gt; [Person]
  followers''' p twitter = [follower t | t &lt;- twitter, followee t == p]
</pre>

<h3>Essayer ces fonctions dans la boule d'interaction</h3>
<pre lang="haskell">main = do
  print $ followers jp twitter
  print $ followers' jp twitter
  print $ followers'' jp twitter
  print $ followers''' jp twitter
</pre>

<h2>Pour aller plus loin</h2>
<ul>
  <li>Trouver les amis</li>
  <li>Recommander des utilisateurs</li>
  <li>Modéliser les twitts et construire la page d'un utilisateur</li>
</ul>

map.hs

Prelude> :t map
map :: (a -> b) -> [a] -> [b]
Prelude> map (*2) [1..10]
[2,4,6,8,10,12,14,16,18,20]

type-length.hs

Prelude> :t length
length :: [a] -> Int