Recherche dans une liste

Extraction

Scheme propose en standard des fonctions de recherche d'informations dans les listes. Ces fonctions sont très pratiques et permettent de réaliser rapidement des mini bases de données.

La fonction Scheme (memq objet liste) retourne la première sous-liste de liste commençant par l'objet objet. Si objet n'est pas trouvé, #f est retourné. La comparaison est effectuée dans memq avec eq?.

On aura par exemple :

Osm> (memq 3 '(1 2 3 4 5))
  => (3 4 5)

Osm> (memq 6 '(1 2 3 4 5))
  => #f

La fonction memv est similaire à memq avec la différence que la comparaison est effectuée avec la fonction eqv?. De même, member fonctionne avec la fonction equal?.

Nous pourrions écrire la fonction memq nous-même avec :

(define (memq objet liste)
  (if (eq? objet (car liste))
     liste
     (memq objet (cdr liste))))

On peut alors imaginer d'écrire une fonction générique de la forme :

(define (generic-mem cmp)
  (define (mem objet liste)
    (if (cmp objet (car liste))
       liste
       (mem objet (cdr liste))))
  mem)

Cette fonction retourne une fonction de la famille de member, où la fonction de comparaison est l'argument de la fonction générique. Il ne reste plus qu'à implémenter les trois fonctions avec :

(define memq   (generic-mem eq?))
(define memv   (generic-mem eqv?))
(define member (generic-mem equal?))

Voilà un exemple de l'utilisation de la forme lambda !

Association

L'autre fonction de recherche (assq objet assocs) retrouve une association dans une liste d'associations assocs étant donné objet. Pour la comparaison, assq utilise la fonction eq?. Par exemple :

Osm> (define assocs
             '((1 . "un")
               (2 . "deux")
               (3 . "trois")
               (4 . "quatre")))
  => #unspecified

Osm> (assq 1 assocs)
  => (1 . "un")

Osm> (assq 4 assocs)
  => (4 . "quatre")

Osm> (assq 5 assocs)
  => #f

Lorsque l'on se souvient que la structure des environnements Scheme sont des couples (symbole valeur), on imagine mieux l'utilité de cette fonction.

Pour la comparaison, la fonction assv utilise quant à elle la fonction eqv? et assoc utilise equal?.

Le lecteur pourra programmer ces fonctions, en utilisant la forme générique, s'il le souhaite.