Les itérateurs permettent d'appliquer un traitement (une fonction) à
tous les termes d'une liste. Ils sont construits selon le schéma de
récursion simple sur les listes.
Étant donnée une liste L d'entiers, supposons que l'on veuille rendre
la liste des éléments de L qui sont pairs. Par exemple:
(filtre-pairs (list 1 2 3 5 8 6)) ->
(2 8 6)
On peut écrire la fonction suivante:
;;;
;;;
(define (filtre-pairs L)
(if (pair? L)
(if (even? (car L))
(cons (car L) (filtre-pairs (cdr L)))
(filtre-pairs (cdr L)))
(list)))
Si l'on veut rendre la liste des éléments de L qui sont impairs,
il faut écrire une autre fonction:
;;;
;;;
(define (filtre-impairs L)
(if (pair? L)
(if (odd? (car L))
(cons (car L) (filtre-impairs (cdr L)))
(filtre-impairs (cdr L)))
(list)))
En fait, toutes ces définitions ont la même forme, autrement dit elles
suivent le même schéma:
;;;
(define (fonction L)
(if (pair? L)
(if (test? (car L))
(cons (car L) (fonction (cdr L)))
(fonction (cdr L)))
(list)))
et on pourrait dire: « étant donnée une fonction de test (qui a
comme donnée un élément de type alpha et qui rend un booléen), une
définition de la fonction qui rend la liste des éléménts d'une liste
donnée qui vérifient ce test peut être obtenue en écrivant... ».
Mais, plutôt que d'écrire une nouvelle fonction à chaque fois que l'on
change le prédicat de filtrage, il vaut mieux écrire une fonction,
paramétrée par le prédicat de filtrage,
filtre (une telle
fonction est dite générique):
;;;
;;;
;;;
(define (filtre test? L)
(if (pair? L)
(if (test? (car L))
(cons (car L)
(filtre test? (cdr L)))
(filtre test? (cdr L)))
(list)))
Noter que le premier argument de cette fonction est une fonction -- plus
précisément un prédicat -- (on dit que cette fonction est une fonctionnelle).
Et alors:
(filtre even? (list 1 2 3 4 5)) ->
(2 4)
(filtre odd? (list 1 2 3 4 5)) ->
(1 3 5)
(filtre integer? (list 2 2.5 3 3.5 4)) ->
(2 3 4)
Dans tous ces exemples, la fonction de test est une fonction
prédéfinie. Comment faire lorsque ce n'est pas le cas? Par exemple,
comment filtrer dans une liste de nombres ceux qui sont supérieurs à
un nombre donné? Il suffit d'écrire un prédicat ad-hoc et appliquer la
fonction
filtre à ce prédicat:
;;;
;;;
(define (sup-4? x)
(> x 4))
(filtre sup-4? (list 5 2.5 4 4.5 3)) ->
(5 4.5)
On veut écrire une définition de la fonction qui rend la liste des carrés des
éléments d'une liste de nombres. Par exemple:
(liste-carres (list 1 2 3 4)) ->
(1 4 9 16)
Après avoir défini la fonction qui rend le carré de sa donnée:
;;;
;;;
(define (carre x)
(* x x))
on peut écrire une définition de la fonction
liste-carres:
;;;
;;;
(define (liste-carres L)
(if (pair? L)
(cons (carre (car L))
(liste-carres (cdr L)))
(list)))
On peut aussi vouloir écrire une définition de la fonction qui rend la liste
des racines carrées des éléments d'une liste de nombres. Par exemple:
(liste-racines-carrees (list 16 25 36)) ->
(4 5 6)
voici une définition de la fonction
liste-racines-carrees:
;;;
;;;
;;;
(define (liste-racines-carrees L)
(if (pair? L)
(cons (sqrt (car L))
(liste-racines-carrees (cdr L)))
(list)))
Toutes ces définitions suivent le même schéma: la fonction
fn-sur-element ayant comme interface:
;;;
la définition de la fonction est:
;;;
(define (fonction L)
(if (pair? L)
(cons (fn-sur-element (car L))
(fonction (cdr L)))
(list)))
On peut encore écrire une fonction générique pour mettre en oeuvre
toutes ces définitions:
;;;
;;;
;;;
(define (map fn L)
(if (pair? L)
(cons (fn (car L))
(map fn (cdr L)))
(list)))
La fonction
map reçoit une
fonction et une liste, et renvoie une liste de même taille, dans
laquelle chaque terme est le résultat de l'application de la fonction.
En utilisant cette fonction, voici la mise en oeuvre des exemples
précédents:
(map carre (list 1 2 3 4)) ->
(1 4 9 16))
(map sqrt (list 16 25 36)) ->
(4 5 6)
et quelques autres exemples d'utilisation:
(map even? (list 1 2 3 4 5)) ->
(#F #T #F #T #F)
(map odd? (list 1 2 3 4 5)) ->
(#T #F #T #F #T)
Remarque:
Noter bien la différence entre
map et
filtre (qui,
toutes les deux, ont comme données une fonction et une liste, la
fonction ayant comme type de données le type des éléments de la liste
donnée, et rendent une liste):
-
pour map, le résultat de la fonction donnée en argument
est d'un type quelconque alors que, pour filtre, le
résultat de la fonction donnée en argument est obligatoirement un
booléen;
- la liste résultat de map est de même longueur que sa
liste donnée alors que la liste résultat de filtre est
d'une longueur inférieure ou égale à celle de sa liste donnée;
- les éléments de la liste résultat de filtre sont des
éléments de sa liste donnée alors que les éléments de la liste
résultat de map sont différents de ceux de sa liste donnée.
Un dernier exemple:
(map list (list 1 2 3 4)) ->
((1) (2) (3) (4))
Remarque
La fonction
map (mais pas
filtre) est une primitive
de Scheme.
Parmi les exemples de récursion simple sur les listes, nous avons vu
la fonction
somme qui somme tous les éléments d'une liste de
nombres. Nous pourrions aussi définir la fonction
produit qui
rend le produit de tous éléments d'une liste de nombres...
Un exemple dont l'interface est plus complexe: on a, au départ, une
somme de
n francs, on a des rentrées et des dépenses, et on veut
connaître le nouveau solde:
(solde 300 (list 100 -60 -30)) ->
310
(solde 300 (list 100.1 -60.2 -30.4)) ->
309.5
Cette fonction peut être définie comme suit:
;;;
;;;
(define (solde s L)
(if (pair? L)
(+ (car L) (solde s (cdr L)))
s))
Notons que
(somme L) est alors égal à
(solde 0 L):
la fonction
solde est plus générale que la fonction
somme.
On fait plus compliqué? Oui: le compte est un compte bancaire et
l'informaticien de service a décidé de mettre les centimes dans sa
poche (bien sûr le compte initial est alors un entier):
(solde-b 300 (list 100.1 -60.2 -30.4)) ->
308
La fonction
solde-b peut être définie, exactement comme la
fonction
solde mais en utilisant, à la place de la fonction
+, la fonction
add-b de spécification:
;;;
;;;
et la définition de
solde-b est alors:
;;;
;;;
;;;
;;;
(define (solde-b s L)
(if (pair? L)
(add-b (car L) (solde-b s (cdr L)))
s))
Noter bien le type des deux fonctions:
-
add-b est de type float * int -> int;
- solde-b est alors obligatoirement de type int * LISTE[float] -> int.
Remarque:
floor et
inexact->exact étant des fonctions
prédéfinies de Scheme de spécifications:
;;;
;;;
;;;
;;;
;;;
;;;
la fonction
add-b peut être définie par :
;;;
;;;
(define (add-b x n)
(inexact->exact (+ (floor x) n)))
Généralisons: la fonction
reduce reçoit une fonction
binaire (de type
a ×
b -->
b), une valeur de
départ (de type
b) et une liste (de type
LISTE[a]), et condense la liste en un unique résultat
(de type
b), en composant la fonction binaire sur les termes de
la liste. Exemples d'utilisation:
(reduce + 0 (list 1 2 3 4 5)) ->
15
(reduce * 1 (list 1 2 3 4 5)) ->
120
(reduce + 300 (list 100.1 -60.2 -30.4)) ->
309.5
(reduce add-b 300 (list 100.1 -60.2 -30.4)) ->
308
La fonction
reduce peut être définie par:
;;;
;;;
;;;
;;;
(define (reduce fn base L)
(if (pair? L)
(fn (car L) (reduce fn base (cdr L)))
base))
On peut donner des exemples compliqués:
(reduce cons (list) (list 1 2 3 4)) ->
(1 2 3 4)
(reduce cons (list 4 5) (list 1 2 3)) ->
(1 2 3 4 5)
(reduce + 0 (map carre (list 1 2 3 4))) ->
30
et encore plus compliqués:
(reduce et #T (map even? (list 1 2 3 4 5 6 7))) ->
#F
(reduce et #T (map odd? (list 1 3 5 7))) ->
#T
la fonction
et étant définie par:
;;;
;;;
(define (et a b)
(and a b))
Remarque: dans l'application de la fonction
reduce, on
ne peut pas utiliser
and car c'est une forme spéciale et non
une fonction.
Un dernier exemple qui utilise les trois itérateurs que nous avons vus
(et qui calcule la somme des carrés des éléments pairs de la liste donnée):
(reduce + 0
(map carre
(filtre even? (list 1 2 3 4 5 6)))) -> 56
