Func' programming - un blog homéopathique

- Vous prendrez bien une petite cuillère de listes ?
Les listes sont extraordinairement versatiles et se marient particulièrement bien avec la programmation fonctionnelle. Bien sûr, elles ne sont pas adaptées à toutes les situations ; mais pour un prototype, pour une première approche d’un problème, elles constituent souvent un bon choix.
Pour les esprits les plus précis, je parle ici de la single-linked list, c’est-à-dire de cette structure dans laquelle chaque élément contient, en plus de sa valeur, un pointeur vers l’élément suivant.

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
struct List {
  int elem ;
  List* next ;
} ;

Comme la liste se termine par un pointeur null, il suffit d’avoir un élément pour savoir comment la parcourir, depuis cet élément jusqu’à la fin. En y réfléchissant un peu, cela veut dire que toute liste est composée soit du pointeur null, soit d’un élément et d’une liste (la liste des éléments suivants). La liste est donc une structure récursive, et c’est pour cette raison qu’elle est tellement utilisée dans la programmation fonctionnelle.

Tête-à-queue
Les langages fonctionnels ont bien sûr chacun leur terminologie pour parler des listes. Certains, comme Haskell ou Ocaml considèrent que la liste a une tête, le premier élément, et une queue, les éléments suivants :

NB : -- marque le début d’un commentaire en Haskell

Code lisp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
head [1, 2, 3] -- = 1
tail [1, 2, 3] -- = [2, 3]

Dans d’autres langages moins imagés, ces fonctions s’appellent first et rest (Clojure, Racket). Enfin, LISP utilise des noms plus cryptiques : car et cdr.
L’élément vide (le pointeur null) est représenté soit par des crochets vides [] (haskell, Ocaml, Erlang) soit par des parenthèses vides : () (LISP).

Construire une liste
Chaque langage a son idiome, mais ce sont toujours les mêmes concepts à l’œuvre. Ainsi pour construire une liste, on agglomère un élément à une liste grâce à un constructeur de liste. En LISP, ce constructeur s’appelle cons :
NB : en LISP, les commentaires sont introduits par ; ;

Code lisp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
(cons 5 () ) ; ; () est l’ensemble vide. = (5)
(cons 4 (cons 5 () ) ) ; ; = (4 5)
(cons 3 (cons 4  (cons 5 () ) ) ) ; ; = (3 4 5)

On peut bien sûr également écrire directement ‘(3 4 5), à condition de ne pas oublier l’apostrophe (je reviendrai sur la question dans un billet rapide sur LISP).
Dans d’autres langages fonctionnels, le constructeur de liste est :
Haksell : (deux-points) –ex : 1 : 2 : 3 : [] => [1, 2, 3]
Erlang | (pipe) – ex 1 | 2 | 3 | [] => [1, 2, 3]
Ocaml : : (deux fois deux-points)
etc.

Liste et récursion
Grâce à sa structure particulière, la liste se prête particulièrement bien à la récursion. Si l’on prend l’exemple du calcul de la longueur d’une liste :
Longueur liste =
Si liste == listeVide alors 0
Sinon 1 + longueur suiteDeLaListe
En Haskell, par exemple :

Code lisp :

Sélectionner tout - Visualiser dans une fenêtre à part

longueur lst = if lst == [] then 0 else 1 + (longeur (tail lst) )

Pour s’exercer un peu sur les listes dans le prochain billet, nous utiliserons LISP (acronyme de LISt Processing !), Common Lisp pour être précis.

Exercices :
- télécharger un EDI pour LISP (vous pouvez chercher lispbox sur google, ou regarder du côté de ClozureCL par exemple) ;
- dans les exercices du précédent billet, je vous proposais de regarder les articles de Wikipedia pour différents langages fonctionnels. Est-ce que l’un d’entre eux vous a particulièrement plu ? Haskell pour son système de type fort ? Erlang, pour le support natif de la programmation distribuée ? LISP, le langage de programmation programmable ? Cherchez un fil de discussion ou des articles de blog pour vérifier que vous frappez à la bonne porte ;
- allez jeter un œil au forum de programmation fonctionnelle sur developpez.com.