Les listesCM2 : listes (17 slides), TD2 et TP2

0Mode d'emploi

• Ce cours suit le CM2 dans l'ordre (les numéros de slides renvoient au PDF de 17 slides), puis ajoute ce que le TD2 et le TP2 utilisent sans que le CM le montre : les paires (pour le TP2), map, foldl, foldr, andmap et ormap (dans des solutions du TD), et filter, que cite la cheatsheet.
• Tout le code a été exécuté dans Racket 8.10. Ce qui suit ; → est ce que DrRacket affiche. Le cours renvoie souvent au PF1 - Chapitre 1 - Cours : relis la partie indiquée si un point te semble flou.
• Les exercices du TD2 et du TP2 sont travaillés à part : cette page ne contient que le cours.
• Attention au copier-coller depuis les PDF. Les slides du CM2 et les solutions du TD affichent une apostrophe typographique (’) au lieu de l'apostrophe droite ('). Collé dans DrRacket, (list->list2 ’(1 2 3 4 5)) donne ’: unbound identifier. Retape les apostrophes, ou mieux, retape le code : c'est en l'écrivant qu'on l'apprend.
• Rythme conseillé :
  • séance 1 : parties 1 à 5 ;
  • séance 2 : parties 6 et 7, puis les questions 1 à 12 du TD (laisse de côté, pour l'instant, les variantes de solutions qui utilisent map, foldl, foldr, andmap ou ormap : c'est la partie 8) ;
  • séance 3 : parties 8 à 12, puis la fin du TD, la slide 17 et le TP.

Plan

1. 1. Pourquoi des listes
2. 2. Écrire une liste avec list et quote
3. 3. Lire une liste avec first et rest
4. 4. Construire une liste avec cons
5. 5. Les paires, quand cons ne fabrique pas une liste
6. 6. Parcourir une liste par récursion
7. 7. La récursivité terminale sur les listes
8. 8. Les fonctions sont des valeurs
9. 9. Les fonctions toutes faites, hors programme
10. 10. Lire les messages d'erreur des listes
11. 11. Ce que le TD2 utilise
12. 12. Checklist avant le DST

1Pourquoi des listes

Jusqu'ici, une valeur Racket était un nombre, un booléen ou une chaîne : une seule chose à la fois. Une liste (list) range plusieurs valeurs, dans un ordre donné, à l'intérieur d'une seule valeur. Tu connais l'idée avec Python :

Mais trois différences changent tout :

1. Une liste Racket ne se modifie jamais. Pas de L.append(4) ni de L[0] = 9 : on fabrique une nouvelle liste (partie 4.5). C'est l'absence d'affectation du chapitre 1 (partie 1.3), appliquée aux listes.
2. On ne lit pas une liste par indice, mais par la tête. Une liste est une chaîne de maillons : on accède directement au premier, et pour atteindre le dixième, on enlève neuf fois le premier. list-ref existe, mais la slide 10 la classe hors programme.
3. La liste vide est le point de départ de tout. Toute liste est construite à partir de '(), et toute fonction sur les listes s'arrête sur '().

2Écrire une liste avec list et quote

2.1 Avec la fonction list (slide 2)

list est une fonction comme les autres : elle évalue ses arguments, puis range leurs valeurs dans une liste.

(list 1 2 3)              ; → '(1 2 3)
(list "a" "b" "c")        ; → '("a" "b" "c")
(list (+ 1 1) (* 2 3))    ; → '(2 6)

DrRacket affiche une liste précédée d'une apostrophe, '(1 2 3), parce que c'est ainsi qu'on l'écrirait dans un programme.

2.2 Avec quote (slide 2)

L'apostrophe, ou quote, dit à Racket : n'évalue pas ce qui suit, c'est une donnée.

'(1 2 3)             ; → '(1 2 3)
(quote (1 2 3))      ; → '(1 2 3)
'((+ 1 1) 3)         ; → '((+ 1 1) 3)

Pourquoi en a-t-on besoin ? Parce qu'au chapitre 1, une parenthèse ouvrante voulait dire « applique » (partie 3.3). Sans l'apostrophe, Racket essaie d'appliquer 1 comme une fonction :

(1 2 3)   ; → erreur : application: not a procedure

La troisième ligne de l'exemple précédent montre la vraie différence avec list : sous l'apostrophe, rien n'est calculé. '((+ 1 1) 3) est une liste de deux éléments, dont le premier est lui-même une liste de trois éléments : le symbole +, puis 1, puis 1. Avec list, (+ 1 1) aurait été calculé et aurait donné 2.

Le premier élément est bien une liste, pas un nombre :

(first '((+ 1 1) 3))   ; → '(+ 1 1)

quote ne peut donc pas être une fonction : une fonction évalue toujours ses arguments avant l'appel (évaluation stricte, partie 3.5 du chapitre 1), et (1 2 3) provoquerait une erreur avant même que quote ne reçoive quoi que ce soit. C'est une forme spéciale, comme if ou define. La slide 2 parle de « la fonction quote » : c'est un abus de langage, voir la partie 12.

2.3 Les symboles (slides 2, 3 et 7)

'a est un symbole (symbol) : un nom utilisé comme une valeur, sans rien derrière. Comme le dit la slide 3, un symbole existe dès qu'on l'écrit, alors qu'une variable n'existe que si on l'a définie avant.

(list 'a 'b 'c)   ; → '(a b c)
'(a b c)          ; → '(a b c)

Sans apostrophe, a est un nom de variable, que Racket cherche :

(list a b c)   ; → erreur : a: unbound identifier

Avec des variables définies (slide 3), la liste contient leurs valeurs :

(define a 2)
(define b (* a a))
(define c (* b b))
(list a b c)   ; → '(2 4 16)

Et voici le piège de la slide 7 : avec des variables définies, l'apostrophe donne quand même des symboles, pas les valeurs.

(define a 1)
(define b 2)
'(a b)       ; → '(a b)
(list a b)   ; → '(1 2)

Un symbole n'est pas une chaîne de caractères : 'a et "a" sont deux valeurs de types différents. Pour comparer des symboles, ou des listes, on utilise equal? ; le = du chapitre 1 ne compare que des nombres.

(equal? 'a 'a)              ; → #t
(equal? "a" 'a)             ; → #f
(equal? '(1 2) (list 1 2))  ; → #t
(= 'a 'a)                   ; → erreur : =: contract violation

2.4 La liste vide (slide 5)

Elle a trois écritures, qui désignent exactement la même valeur, affichée '() :

'()       ; → '()
empty     ; → '()
(list)    ; → '()

2.5 Ce qu'une liste peut contenir

N'importe quoi, et pas forcément des valeurs du même type, comme en Python : des nombres, des chaînes, des symboles, des booléens, et d'autres listes.

'(a "a" 1 #t (2 3))       ; → '(a "a" 1 #t (2 3))
(length '((1 2) (3)))     ; → 2

'((1 2) (3)) contient deux éléments, qui sont deux listes. length ne compte que les éléments du premier niveau.

2.6 Une fonction qui renvoie une liste (slide 4)

Une liste permet à une fonction de renvoyer plusieurs résultats d'un coup. La slide 4 renvoie x, x² et x⁴ :

(define (f x)
  (let* ([x2 (* x x)]
         [x4 (* x2 x2)])
    (list x x2 x4)))
(f 3)   ; → '(3 9 81)

Les deux autres versions de la slide (avec (list x (* x x) (* x x x x)), ou avec des define locaux) donnent le même résultat. La version let* calcule x² une seule fois : c'est la partie 8 du chapitre 1.

(list 1 (+ 1 1) 3)       ; → '(1 2 3)
'(1 (+ 1 1) 3)           ; → '(1 (+ 1 1) 3)
(list 'x "x")            ; → '(x "x")
(length '(a (b c) d))    ; → 3
(define x 5)
(list x 'x)              ; → '(5 x)
'(x x)                   ; → '(x x)

3Lire une liste avec first et rest

3.1 Une tête et un reste (slide 5)

Pense à un train. first donne la tête (head), le premier wagon. rest donne le reste (tail), c'est-à-dire tout le train sauf le premier wagon : c'est encore un train, éventuellement vide.

(first '(1 2 3))   ; → 1
(rest '(1 2 3))    ; → '(2 3)
(rest '(3))        ; → '()

La règle à graver (slide 6) : first renvoie un élément, rest renvoie toujours une liste. C'est l'équivalent de L[0] et de L[1:] en Python. Historiquement, ces fonctions s'appellent car et cdr (slide 5) ; elles existent toujours, on y revient en partie 5.

3.2 Aller chercher plus loin

Pour atteindre le troisième élément, on enlève deux fois la tête, puis on prend la tête de ce qui reste :

(define L '(10 20 30 40))
(first (rest (rest L)))   ; → 30
(cadr L)                  ; → 20
(caddr L)                 ; → 30

cadr (« le car du cdr ») est un raccourci pour (first (rest L)), et caddr pour (first (rest (rest L))). La cheatsheet cite cadr et cddr ; tu peux t'en passer et composer first et rest.

3.3 Le piège de la liste vide (slide 6)

first et rest n'ont de sens que sur une liste d'au moins un élément. Sur la liste vide :

(first empty)   ; → erreur : first: contract violation
(rest '())      ; → erreur : rest: contract violation

first: contract violation
  expected: (and/c list? (not/c empty?))
  given: '()

Lis le message : first attendait « une liste, et pas une liste vide », et on lui a donné '(). D'où la règle qui va structurer toute la partie 6 : on teste toujours empty? avant d'utiliser first ou rest.

3.4 Les listes de listes (slide 6)

Quand les éléments sont des listes, first renvoie une liste (puisque l'élément en est une), et rest renvoie une liste de listes :

(first (list (list 1) (list 2 3)))   ; → '(1)
(rest (list (list 1) (list 2 3)))    ; → '((2 3))

3.5 length, empty? et list? (slides 5 et 7)

(length '(1 2 3))           ; → 3
(empty? '())                ; → #t
(empty? '(1 2 3))           ; → #f
(empty? '(()))              ; → #f
(list? '(1 2))              ; → #t
(list? 5)                   ; → #f
(list? (first '(1 2)))      ; → #f
(list? (rest '(1 2)))       ; → #t

Le piège de la liste : '(()) n'est pas vide. C'est une liste d'un élément, et cet élément est la liste vide. Comme une boîte qui contient une boîte vide : la grande boîte n'est pas vide.

(define L '(10 (20 30) 40))
(first L)                       ; → 10
(rest L)                        ; → '((20 30) 40)
(first (rest L))                ; → '(20 30)
(length L)                      ; → 3
(rest (rest (rest L)))          ; → '()
(first (rest (first (rest L)))) ; → 30
(first (rest (rest (rest L))))  ; → erreur : first: contract violation

4Construire une liste avec cons

4.1 cons ajoute un élément en tête (slide 7)

(cons e L) fabrique une nouvelle liste dont la tête est e et le reste est L.

(cons 1 '(2 3))   ; → '(1 2 3)
(cons 1 empty)    ; → '(1)

Toute liste est en réalité une suite de cons emboîtés, qui se termine par la liste vide. list n'est qu'un raccourci :

(cons 1 (cons 2 (cons 3 '())))   ; → '(1 2 3)

Dessinée, une liste est une chaîne de cellules (cells), chacune avec deux cases : la tête à gauche, et à droite une flèche vers le reste.

'(1 2 3)

 ┌───┬───┐    ┌───┬───┐    ┌───┬───┐
 │ 1 │ ●─┼───>│ 2 │ ●─┼───>│ 3 │ ●─┼───> '()
 └───┴───┘    └───┴───┘    └───┴───┘
 (first)(rest)

first lit la case de gauche de la première cellule, rest suit la flèche. cons fabrique une cellule de plus, au début de la chaîne : c'est pour ça qu'il est instantané, quelle que soit la longueur de la liste.

4.2 La tête est le dernier élément ajouté (slide 7)

Si tu ajoutes 1, puis 2, puis 3 avec cons, chaque nouvel élément passe devant les précédents :

(cons 3 (cons 2 (cons 1 '())))   ; → '(3 2 1)

La liste se lit dans l'ordre inverse de l'ajout (la note de la slide 7). Retiens-le bien : c'est ce qui fera sortir certaines listes à l'envers en partie 7.

4.3 cons, list et append, à ne pas confondre (slides 7 et 8)

C'est la confusion numéro un du chapitre. Compare :

(cons 1 '(2 3))           ; → '(1 2 3)
(list 1 '(2 3))           ; → '(1 (2 3))
(append '(1) '(2 3))      ; → '(1 2 3)
(cons '(1) '(2 3))        ; → '((1) 2 3)
(list '(1) '(2 3))        ; → '((1) (2 3))
(append '(1) '(2 3) '(4)) ; → '(1 2 3 4)

Le réflexe : avant d'écrire, demande-toi ce que tu as en main. Un élément et une liste : cons. Deux listes : append. Des éléments séparés : list. Si un résultat affiche des parenthèses en trop, comme '(1 (2 3)), c'est souvent un list à la place d'un cons ou d'un append.

4.4 Et pour ajouter à la fin ?

Aucune fonction ne le fait directement : cons n'ajoute qu'en tête, et append est fait pour coller des listes. Le piège classique :

(append '(1 2) 3)          ; → '(1 2 . 3)
(append '(1 2) (list 3))   ; → '(1 2 3)
(append 1 '(2 3))          ; → erreur : append: contract violation

Avec un nombre en dernier argument, append ne proteste pas, mais fabrique un objet bizarre, '(1 2 . 3), qui n'est pas une vraie liste (partie 5). Ajouter à la fin coûte cher : append doit recopier toute la première liste, cellule par cellule, pour accrocher la suite. La question 2 du TP2 te fait écrire ta propre fonction.

4.5 Rien n'est jamais modifié

(define L '(2 3))
(cons 1 L)   ; → '(1 2 3)
L            ; → '(2 3)

cons fabrique une nouvelle liste ; L n'a pas bougé. Même chose pour list-set (slide 10), qui renvoie une nouvelle liste avec un élément changé, sans toucher à l'ancienne. En Python, L.append(4) modifie L ; en Racket, jamais. C'est aussi ce qui permet à cons de ne pas recopier L : la nouvelle cellule pointe simplement vers L, qui ne risque pas de changer.

(cons 0 '(1 2))           ; → '(0 1 2)
(list 0 '(1 2))           ; → '(0 (1 2))
(append '(0) '(1 2))      ; → '(0 1 2)
(cons '(0) '(1 2))        ; → '((0) 1 2)
(append '(1 2) '())       ; → '(1 2)
(cons '() '())            ; → '(())
(list '() '())            ; → '(() ())
(append '() '())          ; → '()
(cons 'a (cons 'b (cons 'c '())))   ; → '(a b c)

5Les paires, quand cons ne fabrique pas une liste

Cette partie n'est pas dans le CM, mais la question 3 du TP2 en a besoin : elle attend un résultat comme '(6 . 6).

5.1 La paire pointée

cons fabrique en réalité une paire (pair) : une cellule à deux cases. Si la case de droite contient une liste, le résultat est une liste. Sinon, on obtient une paire pointée (dotted pair), que Racket affiche avec un point.

(cons 6 6)            ; → '(6 . 6)
(list? (cons 6 6))    ; → #f
(pair? (cons 6 6))    ; → #t
(pair? '(1 2))        ; → #t
(pair? '())           ; → #f

'(6 . 6)                  '(6)

 ┌───┬───┐                 ┌───┬───┐
 │ 6 │ 6 │                 │ 6 │ ●─┼───> '()
 └───┴───┘                 └───┴───┘
 une paire, pas une liste  une liste d'un élément

La définition exacte d'une liste devient : une liste est soit '(), soit une paire dont la case de droite contient une liste. Ce qui explique ces deux affichages :

'(1 . (2 . (3 . ())))   ; → '(1 2 3)
(cons 1 (cons 2 3))     ; → '(1 2 . 3)

Le premier est une vraie liste écrite sous forme de paires emboîtées : Racket l'affiche normalement. Le second se termine par 3 au lieu de '() : c'est une liste impropre (improper list), et le point montre l'endroit où la chaîne ne finit pas par la liste vide. Quand un point apparaît dans un de tes résultats, c'est qu'une valeur qui n'est pas une liste a atterri dans une case de droite : souvent un (append L 3) au lieu de (append L (list 3)) (partie 4.4).

5.2 car et cdr pour lire une paire

first et rest refusent une paire qui n'est pas une liste. Il faut car (la case de gauche) et cdr (la case de droite), les anciens noms cités par la slide 5 :

(first (cons 6 7))   ; → erreur : first: contract violation
(car (cons 6 7))     ; → 6
(cdr (cons 6 7))     ; → 7
(car '(1 2 3))       ; → 1
(cdr '(1 2 3))       ; → '(2 3)

car et cdr marchent sur n'importe quelle paire, donc aussi sur les listes non vides, où ils font la même chose que first et rest. La différence : first et rest vérifient qu'on leur donne une vraie liste non vide, ce qui donne des messages d'erreur plus clairs. length refuse aussi les paires pointées :

(length (cons 6 7))   ; → erreur : length: contract violation
(car '())             ; → erreur : car: contract violation

5.3 À quoi servent les paires

À renvoyer deux valeurs dans une seule, comme un return (a, b) en Python :

(define (div-euclide a b)
  (cons (quotient a b) (remainder a b)))
(div-euclide 17 5)          ; → '(3 . 2)
(car (div-euclide 17 5))    ; → 3
(cdr (div-euclide 17 5))    ; → 2

Ne confonds pas une paire et une liste de deux éléments. '(3 . 2) est une seule cellule ; '(3 2) en contient deux, puisque c'est (cons 3 (cons 2 '())). Le deuxième élément d'une paire se lit avec cdr ; celui d'une liste de deux éléments, avec (first (rest L)), ou cadr.

(cons 1 2)                     ; → '(1 . 2)
(cons 1 '(2))                  ; → '(1 2)
(car (cons 1 2))               ; → 1
(cdr (cons 1 '(2)))            ; → '(2)
(list? (cons 1 2))             ; → #f
(pair? '(1))                   ; → #t
(cons (cons 1 2) (cons 3 4))   ; → '((1 . 2) 3 . 4)
(first (cons 1 2))             ; → erreur : first: contract violation

6Parcourir une liste par récursion

C'est le cœur du chapitre, et des slides 15 et 16.

6.1 La même méthode qu'au chapitre 1

Le gabarit (template) de presque toutes les fonctions du chapitre :

(define (f x)
  (if (empty? x)
      réponse-pour-la-liste-vide
      (combiner (first x) (f (rest x)))))

Et les quatre questions du chapitre 1 (partie 9.3), adaptées aux listes :

1. Que doit renvoyer f pour la liste vide ? Souvent l'élément neutre : 0 pour une somme, 1 pour un produit, '() quand on construit une liste, #f quand on cherche.
2. Si je connais (f (rest x)), la réponse pour le reste, comment obtenir (f x) avec (first x) ? C'est l'acte de confiance : ne simule pas tous les appels, suppose que l'appel sur le reste est juste.
3. Est-ce que j'appelle f sur (rest x), une liste plus courte ? Alors la fonction termine.
4. Teste sur '(), sur une liste d'un élément, puis sur une liste de trois.

Avant tout first ou rest, un test doit garantir que la liste n'est pas vide, puisqu'ils échouent sur la liste vide (partie 3.3) : c'est pour ça que (empty? x) vient en général en premier.

6.2 Réduire une liste à une valeur

Le nombre d'éléments. Question 1 : une liste vide a 0 élément. Question 2 : si je connais la longueur du reste, j'ajoute 1.

(define (longueur x)
  (if (empty? x)
      0
      (+ 1 (longueur (rest x)))))
(longueur '(a b c))   ; → 3
(longueur '())        ; → 0

(longueur '(a b c))
(+ 1 (longueur '(b c)))
(+ 1 (+ 1 (longueur '(c))))
(+ 1 (+ 1 (+ 1 (longueur '()))))
(+ 1 (+ 1 (+ 1 0)))
3

Les éléments eux-mêmes ne servent pas : on les compte, c'est tout, d'où l'absence de (first x). Pour la somme, en revanche, on ajoute la tête au résultat sur le reste :

(define (somme x)
  (if (empty? x)
      0
      (+ (first x) (somme (rest x)))))
(somme '(4 5 6))   ; → 15

(somme '(4 5 6))
(+ 4 (somme '(5 6)))
(+ 4 (+ 5 (somme '(6))))
(+ 4 (+ 5 (+ 6 (somme '()))))
(+ 4 (+ 5 (+ 6 0)))
15

Compare avec la somme du chapitre 1 (partie 9.3) : même forme, avec (first x) à la place de n et (rest x) à la place de (- n 1).

6.3 Chercher dans une liste (slide 15)

La slide 15 décrit d'abord la version itérative, « non désirable en fonctionnel » : tant que la liste n'est pas vide, si la tête est l'élément cherché, on renvoie vrai ; après la boucle, on renvoie faux. Puis la version récursive : si la liste est vide, faux ; si la tête est l'élément, vrai ; sinon, on cherche dans le reste.

(define (isin? elt x)
  (if (empty? x)
      #f
      (if (equal? elt (first x))
          #t
          (isin? elt (rest x)))))
(isin? 2 '(1 2 3))    ; → #t
(isin? 4 '(1 2 3))    ; → #f
(isin? 'b '(a b c))   ; → #t

Il y a deux façons de s'arrêter : la liste est vide (pas trouvé), ou la tête est l'élément (trouvé, inutile de continuer). J'ai écrit equal? là où la slide écrit = : avec =, la fonction ne marche que sur des nombres, et (isin? 'b '(a b c)) provoque =: contract violation. Attention aussi, la question 11 du TD place les arguments dans l'autre ordre, la liste d'abord : suis toujours l'énoncé (partie 12).

La même fonction avec and et or, qui s'arrêtent dès que le résultat est connu (chapitre 1, partie 5.3) :

(define (isin? elt x)
  (and (not (empty? x))
       (or (equal? elt (first x))
           (isin? elt (rest x)))))
(isin? 3 '(1 2 3))   ; → #t

Dans les deux versions, l'appel récursif est directement le résultat : isin? est récursive terminale, comme le dit la slide 16.

6.4 Transformer chaque élément (slide 16)

(define (apply-fun x fun)
  (if (empty? x)
      empty
      (cons (fun (first x)) (apply-fun (rest x) fun))))
(apply-fun '(1 2 3 4 5) add1)   ; → '(2 3 4 5 6)

add1 ajoute 1 à un nombre (et sub1 retire 1). Le paramètre fun reçoit une fonction : la partie 8 y revient. La trace montre comment la nouvelle liste se construit :

(apply-fun '(1 2 3) add1)
(cons 2 (apply-fun '(2 3) add1))
(cons 2 (cons 3 (apply-fun '(3) add1)))
(cons 2 (cons 3 (cons 4 (apply-fun '() add1))))
(cons 2 (cons 3 (cons 4 '())))
'(2 3 4)

La nouvelle liste est fabriquée au retour, par les cons en attente : c'est pour ça que la slide 16 dit qu'apply-fun est enveloppée. Le cas de base renvoie empty, qui devient la fin de la nouvelle liste. La règle à retenir : quand une fonction construit une liste, le cas de base renvoie '() et le cas récursif fait (cons quelque-chose (f (rest x))).

6.5 Garder certains éléments

Trois cas : la liste est vide ; on garde la tête ; on l'ignore.

(define (garde-pairs x)
  (cond [(empty? x) empty]
        [(even? (first x)) (cons (first x) (garde-pairs (rest x)))]
        [else (garde-pairs (rest x))]))
(garde-pairs '(1 2 3 4 5 6))   ; → '(2 4 6)
(garde-pairs '(1 3))           ; → '()

La deuxième ligne garde la tête (avec cons), la troisième la laisse tomber (on continue simplement sur le reste). Ce schéma en trois lignes sert à supprimer un élément (question 12 du TD), à filtrer (partie 8), et à beaucoup d'autres choses.

6.6 Quand la liste vide n'a pas de réponse

Le plus petit élément de '() n'existe pas : aucune valeur ne convient comme cas de base. On prend alors pour cas de base la liste d'un seul élément, testée par (empty? (rest x)) :

(define (minimum x)
  (if (empty? (rest x))
      (first x)
      (min (first x) (minimum (rest x)))))
(minimum '(5 3 8 1 4))   ; → 1
(minimum '(7))           ; → 7

(minimum '()) provoque une erreur, et c'est normal : il n'y a pas de minimum. Les solutions du TD testent la même chose avec (= (length x) 1). Ça marche, mais length parcourt toute la liste à chaque appel : pour une liste de n éléments, n appels qui font chacun jusqu'à n pas. (empty? (rest x)) répond immédiatement : prends cette habitude.

6.7 Parcourir avec un compteur

Quand la position des éléments compte, on transporte un compteur qui augmente pendant que la liste raccourcit. Par exemple, pour numéroter chaque élément avec une paire (partie 5) :

(define (numerote x [i 0])
  (if (empty? x)
      empty
      (cons (cons i (first x)) (numerote (rest x) (+ i 1)))))
(numerote '(a b c))   ; → '((0 . a) (1 . b) (2 . c))

La valeur par défaut [i 0] (chapitre 1, partie 10.2) fait partir le compteur de 0. Les solutions du TD préfèrent une fonction auxiliaire, comme (f x p) à la question 5 : les deux formes sont présentées en partie 7.1. Deux choses changent à chaque appel : la liste perd sa tête, le compteur gagne 1. Les questions 4, 5, 9 et 20 du TD reposent sur cette idée.

6.8 Deux listes à la fois

Pour additionner deux listes terme à terme, on avance dans les deux en même temps, et on s'arrête dès que l'une est vide :

(define (sommes x y)
  (if (or (empty? x) (empty? y))
      empty
      (cons (+ (first x) (first y)) (sommes (rest x) (rest y)))))
(sommes '(1 2 3) '(10 20 30))   ; → '(11 22 33)
(sommes '(1 2) '(10 20 30))     ; → '(11 22)

Dans d'autres fonctions à deux listes, on n'avance que dans la première : c'est le cas de merge (question 8 du TD) et de my-append (slide 17).

6.9 Listes de listes, la récursion en profondeur

Quand les éléments peuvent eux-mêmes être des listes, il faut parfois descendre aussi dans (first x) : c'est le cas de la question 6 du TD (la question 7, elle, se contente de repérer une sous-liste). Par exemple, pour compter les nombres à tous les niveaux :

(define (compte-nombres x)
  (cond [(empty? x) 0]
        [(list? (first x)) (+ (compte-nombres (first x))
                              (compte-nombres (rest x)))]
        [else (+ 1 (compte-nombres (rest x)))]))
(compte-nombres '(1 (2 3) ((4 5)) ()))   ; → 5
(length '(1 (2 3) ((4 5)) ()))           ; → 4

Trois cas : la liste est vide ; la tête est une liste, et l'on fait deux appels récursifs, l'un dans la tête, l'autre dans le reste ; la tête est un simple élément. length, elle, ne compte que les quatre éléments du premier niveau. Une liste de listes est en fait un arbre (tree) :

'(1 (2 3) ((4 5)) ())

          ●
   ┌──────┼──────┬──────┐
   1      ●      ●      ()
         / \     │
        2   3    ●
                / \
               4   5

Avec deux appels récursifs, on parle de récursivité en arbre (tree recursion), comme pour fibo au chapitre 1 (exercice F9).

(define (produit x)
  (if (empty? x)
      1
      (* (first x) (produit (rest x)))))
(produit '(2 3 4))   ; → 24
(produit '())        ; → 1

(define (compte e x)
  (cond [(empty? x) 0]
        [(equal? e (first x)) (+ 1 (compte e (rest x)))]
        [else (compte e (rest x))]))
(compte 'a '(a b a c a))   ; → 3

(define (garde-negatifs x)
  (cond [(empty? x) empty]
        [(negative? (first x)) (cons (first x) (garde-negatifs (rest x)))]
        [else (garde-negatifs (rest x))]))
(garde-negatifs '(3 -1 0 -5 2))   ; → '(-1 -5)

7La récursivité terminale sur les listes

7.1 Réduire avec un accumulateur

Même méthode qu'au chapitre 1 (partie 10.3) : l'accumulateur part de la réponse pour la liste vide, et l'opération se fait avant l'appel.

(define (somme-t x [acc 0])
  (if (empty? x)
      acc
      (somme-t (rest x) (+ acc (first x)))))
(somme-t '(4 5 6))   ; → 15

(somme-t '(4 5 6) 0)
(somme-t '(5 6) 4)
(somme-t '(6) 9)
(somme-t '() 15)
15

Les solutions du TD écrivent l'accumulateur autrement : avec une fonction auxiliaire locale, qui le cache à l'utilisateur (chapitre 1, partie 10.4). C'est le (define (f x p) ...) de la question 5, ou le (define (f x y i) ...) de la question 9 :

(define (somme-t x)
  (define (f x acc)
    (if (empty? x)
        acc
        (f (rest x) (+ acc (first x)))))
  (f x 0))
(somme-t '(4 5 6))   ; → 15

Les deux formes sont justes. Rappel du chapitre 1 : la slide 25 du CM1 classe les valeurs par défaut hors programme, alors que ton enseignant s'en sert. Sache écrire les deux, et demande-lui laquelle il attend au DST.

7.2 Construire avec un accumulateur, la liste sort à l'envers

Essayons de recopier une liste avec un accumulateur :

(define (copie-t x [acc '()])
  (if (empty? x)
      acc
      (copie-t (rest x) (cons (first x) acc))))
(copie-t '(1 2 3))   ; → '(3 2 1)

(copie-t '(1 2 3) '())
(copie-t '(2 3) '(1))
(copie-t '(3) '(2 1))
(copie-t '() '(3 2 1))
'(3 2 1)

On prend les éléments par la gauche, mais cons place chacun en tête de l'accumulateur : le dernier pris se retrouve devant (partie 4.2). Cette fonction est donc exactement reverse (slide 8). C'est une loi générale : une récursion terminale qui construit une liste avec cons la fabrique à l'envers. C'est la même raison que pour miroir, dans l'exercice G5 du chapitre 1.

7.3 Trois façons de retrouver le bon ordre

Première façon : retourner une seule fois, à la fin, avec reverse :

(define (garde-pairs-t x [acc '()])
  (cond [(empty? x) (reverse acc)]
        [(even? (first x)) (garde-pairs-t (rest x) (cons (first x) acc))]
        [else (garde-pairs-t (rest x) acc)]))
(garde-pairs-t '(1 2 3 4 5 6))   ; → '(2 4 6)

C'est ce que fait ton enseignant dans la solution 1 de la question 9 du TD. Attention au mot une seule fois : si la fonction s'appelle aussi sur des sous-listes (la récursion en profondeur de la partie 6.9) et retourne l'accumulateur dans son cas de base, il est retourné plusieurs fois. C'est l'erreur de la troisième solution de la question 6 du TD (partie 12).

Deuxième façon : ajouter à la fin avec append. (append acc (list (first x))) garde l'ordre, mais chaque append recopie tout l'accumulateur, soit environ n²/2 copies pour n éléments. La solution de la question 13 du TD fait ainsi.

Troisième façon : garder la version enveloppée. Pour construire une liste, (cons ... (f (rest x))) donne le bon ordre sans effort, et c'est souvent le plus clair : c'est le conseil de la slide 35 du CM1, commencer par la version simple.

Quand l'ordre ne compte pas (somme, produit, longueur, maximum, recherche), l'accumulateur ne pose aucun problème.

7.4 En résumé

(copie-t '(a b c) '())
(copie-t '(b c) '(a))
(copie-t '(c) '(b a))
(copie-t '() '(c b a))
'(c b a)

(define (produit-t x [acc 1])
  (if (empty? x)
      acc
      (produit-t (rest x) (* acc (first x)))))
(define (longueur-t x [acc 0])
  (if (empty? x)
      acc
      (longueur-t (rest x) (+ acc 1))))
(produit-t '(2 3 4))   ; → 24
(longueur-t '(a b c))  ; → 3

8Les fonctions sont des valeurs

Le CM s'en sert sans s'y arrêter (aux slides 9 et 13, build-list, list-update et sort reçoivent une fonction), puis le montre avec apply-fun à la slide 16. La cheatsheet (rubrique « map et fold ») présente la plupart des fonctions de cette partie, et plusieurs solutions du TD s'en servent.

8.1 Passer une fonction en argument (slide 16)

Dans apply-fun, le paramètre fun reçoit une fonction. En Racket, une fonction est une valeur comme une autre : on peut la passer en argument, la renvoyer, la ranger dans une liste. C'est comme en Python, où l'on peut passer len à map.

(define (apply-fun x fun)
  (if (empty? x)
      empty
      (cons (fun (first x)) (apply-fun (rest x) fun))))
(define (carre v) (* v v))
(apply-fun '(1 2 3) carre)                    ; → '(1 4 9)
(apply-fun '(1 2 3) (lambda (v) (* 10 v)))    ; → '(10 20 30)

La dernière ligne passe une fonction fabriquée sur place, sans nom : (lambda (v) (* 10 v)) (chapitre 1, partie 6.4). La slide 9 en utilise aussi, avec build-list et list-update. Le chapitre 1 la classe hors programme : sache la lire. Pour t'en passer, il suffit de nommer la fonction d'abord, (define (fois10 v) (* 10 v)), puis d'écrire (apply-fun '(1 2 3) fois10).

Les opérateurs sont des fonctions eux aussi, donc on peut les passer :

(define (applique op a b) (op a b))
(applique + 2 3)     ; → 5
(applique < 2 3)     ; → #t
(applique max 2 3)   ; → 3

C'est exactement ce que fait la question 19 du TD : (chk? 0 < '(1 2 3 4 5)) reçoit la fonction < en deuxième argument.

Le piège : on passe la fonction sans parenthèses. carre est la fonction ; (carre) est un appel, qui échoue ici faute d'argument (chapitre 1, partie 6.3, myr contre (myr)).

(define (apply-fun x fun)
  (if (empty? x)
      empty
      (cons (fun (first x)) (apply-fun (rest x) fun))))
(define (carre v) (* v v))
(apply-fun '(1 2 3) (carre))   ; → erreur : carre: arity mismatch

Une fonction qui prend ou renvoie une fonction s'appelle une fonction d'ordre supérieur (higher-order function). Racket en fournit plusieurs pour les listes.

8.2 map, l'apply-fun de Racket

(map f L) applique f à chaque élément de L. La fonction vient en premier, la liste ensuite :

(map sqrt '(1 4 9))                    ; → '(1 2 3)
(map add1 '(1 2 3))                    ; → '(2 3 4)
(map (lambda (v) (* v v)) '(1 2 3))    ; → '(1 4 9)
(map + '(1 2) '(10 20))                ; → '(11 22)
(map + '(1 2) '(10 20 30))             ; → erreur : map: all lists must have same size

Avec plusieurs listes, map prend un élément de chacune : l'avant-dernière ligne refait la fonction sommes de la partie 6.8, à une différence près, que montre la dernière ligne : map exige des listes de même longueur, alors que sommes s'arrête à la fin de la plus courte. En Python, (map f L) s'écrit [f(v) for v in L].

8.3 filter, garder ceux qui vérifient un prédicat

(filter even? '(1 2 3 4 5 6))               ; → '(2 4 6)
(filter (lambda (v) (> v 2)) '(1 2 3 4))    ; → '(3 4)

C'est garde-pairs (partie 6.5), avec n'importe quel prédicat. En Python : [v for v in L if p(v)].

8.4 foldl et foldr, plier une liste

Plier (fold) une liste, c'est combiner tous ses éléments avec une fonction, en partant d'une valeur initiale qui joue le rôle d'accumulateur. La fonction reçoit l'élément, puis l'accumulateur :

(foldl f init '(a b c))   =   (f c (f b (f a init)))     de gauche à droite
(foldr f init '(a b c))   =   (f a (f b (f c init)))     de droite à gauche

(foldl + 0 '(1 2 3))         ; → 6
(foldl cons '() '(1 2 3))    ; → '(3 2 1)
(foldr cons '() '(1 2 3))    ; → '(1 2 3)

(foldl cons '() '(1 2 3)) calcule (cons 3 (cons 2 (cons 1 '()))) : la liste à l'envers. (foldr cons '() '(1 2 3)) calcule (cons 1 (cons 2 (cons 3 '()))) : une copie. Avec une opération où l'ordre compte, la différence saute aux yeux :

(foldl (lambda (e acc) (+ (* 10 acc) e)) 0 '(1 2 3))   ; → 123
(foldr (lambda (e acc) (+ (* 10 acc) e)) 0 '(1 2 3))   ; → 321

foldl est la récursivité terminale avec accumulateur de la partie 7 ; foldr est la version enveloppée. Avec + ou × sur des entiers, les deux donnent le même résultat. Avec des flottants, chaque opération arrondit, si bien que l'ordre des additions peut changer le dernier chiffre (la partie 12 montre un autre effet de ces arrondis, à la question 22) :

(foldl + 0.0 '(0.1 0.2 0.3))   ; → 0.6000000000000001
(foldr + 0.0 '(0.1 0.2 0.3))   ; → 0.6

La question 21 du TD utilise (foldl + 0.0 x) : la valeur initiale 0.0 rend la somme inexacte, donc la moyenne décimale (chapitre 1, partie 4.1) :

(/ (foldl + 0 '(3 3 4)) 3)      ; → 10/3
(/ (foldl + 0.0 '(3 3 4)) 3)    ; → 3.3333333333333335

8.5 andmap et ormap, « pour tout » et « il existe »

(andmap even? '(2 4 6))   ; → #t
(andmap even? '(1 3 6))   ; → #f
(ormap even? '(1 3 6))    ; → #t
(andmap even? '())        ; → #t
(ormap even? '())         ; → #f

andmap répond à « tous les éléments vérifient-ils le prédicat ? » ; ormap, à « au moins un le vérifie-t-il ? ». Ce sont le ∀ et le ∃ de ton cours La logique, depuis le tout début (partie 8.2), ou all() et any() en Python. Sur la liste vide, andmap répond vrai : aucun élément ne vient contredire la propriété, c'est la vérité par vacuité de la partie 8.3 de ce même cours de logique (« tous les dragons de ma chambre sont verts »). Et ormap répond faux : il n'y a aucun élément pour la vérifier. Les deuxièmes solutions des questions 7, 11 et 19 du TD s'en servent.

8.6 Quand t'en servir

Toutes ces fonctions, sauf foldr, sont sur la cheatsheet, ton seul document au DST : tu les auras sous les yeux. Mais un énoncé peut interdire une fonction toute faite (le TP2 interdit make-list, plusieurs questions du TD interdisent celle qu'elles font réécrire), et les « fonctions utiles » indiquées sous chaque question disent ce qui est attendu : foldl est suggérée aux questions 21 et 22, et map à la question 22, alors que la plupart des autres questions ne citent que des fonctions de base, comme empty?, cons, first et rest. Dans le doute, sache toujours écrire la version récursive : c'est tout l'objet de la slide 17.

(map (lambda (v) (* 2 v)) '(1 2 3))   ; → '(2 4 6)
(filter odd? '(1 2 3 4 5))            ; → '(1 3 5)
(foldl + 0 (map add1 '(1 2 3)))       ; → 9
(andmap positive? '(1 -2 3))          ; → #f
(ormap negative? '(1 -2 3))           ; → #t
(foldl cons '() '(a b))               ; → '(b a)
(foldr cons '() '(a b))               ; → '(a b)
(foldl max 0 '(3 9 2))                ; → 9
(define (garde-pairs x) (filter even? x))
(define (somme x) (foldl + 0 x))
(garde-pairs '(1 2 3 4))              ; → '(2 4)
(somme '(4 5 6))                      ; → 15

9Les fonctions toutes faites, hors programme

Les slides 8 à 14 présentent des fonctions marquées hors programme. Il faut savoir ce qu'elles renvoient exactement, car la slide 17 (et le TD) te demandent de les réécrire.

(remove 2 '(1 2 3 2))                ; → '(1 3 2)
(member 5 '(1 2 3 4))                ; → #f
(index-of '(1 2 3 4) 5)              ; → #f
(take '(1 2) 5)                      ; → erreur : take: contract violation
(define A '(1 2 3 4 5))
(define B (list-set A 1 42))
A                                    ; → '(1 2 3 4 5)
B                                    ; → '(1 42 3 4 5)
(if (member 3 '(1 2 3)) "oui" "non") ; → "oui"

member ne renvoie pas #t, mais une liste. Ça suffit pour un test, puisque toute valeur autre que #f compte comme vraie (chapitre 1, partie 5.4).

10Lire les messages d'erreur des listes

11Ce que le TD2 utilise

12Checklist avant le DST

Tu dois pouvoir, sur papier :

• écrire une liste avec list ou avec l'apostrophe, et dire ce qui est évalué (parties 2.1 et 2.2) ;
• distinguer un symbole, une chaîne et une variable (partie 2.3) ;
• prédire first, rest et cadr sur une liste de listes (partie 3) ;
• choisir entre cons, list et append (partie 4.3), et repérer un point ou des parenthèses en trop dans un résultat (parties 5.1 et 10) ;
• expliquer une paire pointée, et lire ses deux cases avec car et cdr (partie 5) ;
• écrire une fonction sur une liste avec le gabarit et les quatre questions, et donner sa trace (parties 6.1 et 6.2) ;
• reconnaître la famille d'une question : réduire, chercher, transformer, garder, compteur, deux listes, profondeur (partie 6) ;
• passer d'une version enveloppée à une version terminale, et savoir quand la liste sort à l'envers (partie 7) ;
• passer une fonction en argument, et utiliser map, filter, foldl, foldr, andmap et ormap (partie 8) ;
• connaître le comportement exact des fonctions hors programme, pour pouvoir les réécrire (partie 9 et slide 17) ;
• lire les messages d'erreur de la partie 10.

Et après ? La cheatsheet contient aussi ce qui vient ensuite : match, les images (2htdp/image) et la tortue (graphics/turtles). match sert justement à découper une liste en tête et reste en une seule ligne : tout ce chapitre te servira encore.