Opérations sur les listes

Dans cette section, nous allons mettre en pratique nos connaissances pour écrire en Scheme quelques fonctions de la bibliothèque standard.

Retournement : reverse

La fonction reverse prend une liste comme argument et retourne une nouvelle liste dont les éléments sont placés en ordre inverse :

Osm> (reverse (list 1 2 3))
  => (3 2 1)

La fonction reverse peut être écrite en Scheme de la manière suivante :

(define (reverse liste)
 (let ((résultat '()))
   (do ((ptr liste (cdr ptr)))
       ((null? ptr))
     (set! résultat
           (cons (car ptr)
                 résultat)))
    résultat))

Cette fonction commence par définir le résultat comme étant la liste vide. Puis elle parcourt tous les éléments de la liste et construit le résultat au fur et à mesure. Comme le premier élément est placé dans le résultat en premier, la liste obtenue est dans l'ordre inverse de la liste donnée en argument.

Ce n'est pas une fonction récursive car rien dans sa définition ne fait appel à la fonction qui est en train d'être définie.

Longueur : length

La fonction length calcule la longueur d'une liste, c'est à dire le nombre d'éléments qu'elle contient. Elle s'utilise comme suit :

Osm> (length (list 1 2 3))
  => 3

Cette fonction provoque une erreur si son argument n'est pas une liste. Ecrivons nous-mêmes la fonction length :

(define (length object) 
 (cond ((null? ojbect)    ; cas 1
        0)
       ((pair? object)    ; cas 2
         (+ 1 (length (cdr object))))
       (else              ; cas 3
        (car object))))

La fonction length est une fonction où l'on distingue trois cas :

1. l'objet est la liste est vide : dans ce cas, le résultat est la longueur de la liste vide, c'est à dire zéro ;
2. l'objet est une paire : dans ce cas, le résultat est 1 additionné à la longueur du reste de la liste ;
3. l'objet n'est ni la liste vide, ni une paire : c'est un cas d'erreur que nous provoquons en appliquant la fonction car à l'objet, ce qui va à coup sûr provoquer une erreur.

Cette fonction est une fonction récursive : en effet, la fonction définie se rappelle elle-même dans le deuxième cas. Décrivons les appels successifs à cette fonction sur un cas concret :

(length (list 1 2 3))
= (+ 1 (length (cdr '(1 2 3)))
= (+ 1 (length '(2 3))
= (+ 1 (+ 1 (length '(cdr 2 3))))
= (+ 1 (+ 1 (length '(3))))
= (+ 1 (+ 1 (+ 1 (length (cdr '(3)))))
= (+ 1 (+ 1 (+ 1 (length '())))
= (+ 1 (+ 1 (+ 1 0))
= 3

On remarque que le système Scheme conserve les additions successives jusqu'à ce que le calcul de la longueur de la liste vide ne soit effectué. C'est la raison pour laquelle cette fonction n'est pas à récursivité terminale. On comparera la liste des appels successifs à ceux produit par la fonction for-each décrite plus bas.

Concaténation : append

La fonction append permet de concaténer plusieurs listes entre elles et retourne la nouvelle liste ainsi formée. La fonction décrite dans la norme permet de donner à append un nombre quelconque de listes à concaténer.

Osm> (append (list 1 2 3)
             (list 4 5 6)
             (list 7 8 9))
  => (1 2 3 4 5 6 7 8 9)

Pour notre part, nous nous contenterons d'écrire la fonction append-2 qui concatène seulement deux listes :

(define (append-2 l1 l2)
 (cond ((null? l1)      ; cas 1
         (if (list? l2) 
          l2
          (car l2)))
       ((pair? l1)      ; cas 2
         (cons (car l1)
               (append-2 (cdr l1) l2)))
       (else            ; cas 3
        (car l1))))

Cette fonction est aussi définie par trois cas :

1. l1 est las liste vide : dans ce cas, le résultat est la seconde liste. La fonction vérifie que l2 est bien une liste bien formée ;
2. l1 est une paire : là, le résultat est une nouvelle paire formée du premier élément de l1 et de la concaténation de reste de l1 et de l2 ;
3. l1 n'est ni une paire, ni la liste vide : il s'agit d'un cas d'erreur qui va être provoqué par l'application de car à l1.

La fonction qui vient d'être définie est récursive car elle s'applique elle-même dans le second cas.

Application d'une fonction aux éléments : for-each

Avec for-each, il est possible d'appliquer une fonction à tous les éléments d'une ou plusieurs listes :

Osm> (define (f-1 x)
       (display x)
       (newline))
  => #unspecified

Osm> (for-each f-1 (list 1 2 3))
  => 1
     2
     3
     #unspecified

Osm> (define (f-2 x y)
       (display x)
       (display #\,)
       (display y)
       (newline))
  => #unspecified

Osm> (for-each f-2 (list 1 2 3)
                   (list #\a #\b #\c))
  => 1,a
     2,b
     3,c
     #unspecified

Pour notre part, nous nous contenterons d'écrire la fonction for-each-1 qui applique une fonction à une seule liste :

(define (for-each-1 fonction liste)
 (if (pair? liste)
   (begin
    (fonction (car liste))
    (for-each-1 fonction (cdr liste)))))

Quels sont les appels successifs à cette fonction sur un cas concret :

(for-each-1 f-1 (list 1 2 3))
= (for-each-1 f-1 (cdr '(1 2 3))
= (for-each-1 f-1 '(2 3)
= (for-each-1 f-1 (cdr '(2 3))
= (for-each-1 f-1 '(3)
= (for-each-1 f-1 (cdr '(3))
= (for-each-1 f-1 '()

Les appels à la fonction f-1 ne sont pas indiqués dans la mesure où ils n'interviennent pas dans le processus récursif. On remarque qu'un appel à la fonction for-each-1 se traduit par plusieurs appels à cette même fonction. Mais, contrairement à length, aucun résultat intermédiaire n'est conservé. On aurait pu écrire for-each-1 en C de la manière suivante:

void for-each-1 (void (* fonc)(Objet),
                 Objet liste) {
Label:
 if (pair? (liste)) {
   fonc (car (liste));
   goto Label;
 }
}

Dans cette définition, l'appel récursif a été supprimé et remplacé par un saut goto. Les environnements Scheme détectent ce type de récursivité terminale et la remplacent de manière interne par un saut.

Application d'une fonction aux éléments, avec capture des résultats : map

La fonction map fonctionne de manière similaire à for-each. Mais elle retourne une liste formée des résultats des applications aux éléments de la ou des listes :

Osm> (define (f x)
       (+ x 10))
  => #unspecified

Osm> (map f (list 1 2 3))
  => (11 12 13)

Ici, on va définir la fonction map-1 qui applique une fonction à une seule liste :

(define (map-1 fonction liste)
 (if (pair? liste)
   (cons (fonction (car ptr))
         (map-1 fonction (cdr liste)))
   '()

Comme le résultat de l'appel récursif est utilisé pour construire la liste résultat, cette fonction n'est pas à récursivité terminale. Donc, dans les cas où l'on n'a pas besoin de conserver les résultats intermédiaires, on préfèrera for-each.