Manipulez des listes

Au chapitre 4, nous avons représenté un itinéraire par un terme comme par(laval, par(le_mans, rien)). Cela fonctionne, mais c’est lourd à écrire et chaque programme invente sa propre convention. Prolog fournit une structure standard pour les suites d’éléments, avec une syntaxe dédiée : la liste. C’est la structure de données reine du langage.

Dans ce chapitre, vous allez comprendre comment une liste est faite, écrire les prédicats classiques qui les manipulent, et découvrir la technique de l’accumulateur. Notre fil rouge : une portion de la ligne a du métro de Rennes.

% les stations de la ligne a, de J.F. Kennedy vers Gares
ligne_a([j_f_kennedy, villejean_universite, pontchaillou, anatole_france,
         sainte_anne, republique, charles_de_gaulle, gares]).

Une liste, c’est une tête et une queue

Une liste est une structure récursive, définie à partir de deux éléments :

une constante qui représente la liste vide, notée [] ;
un foncteur binaire, le constructeur (historiquement noté .), dont le premier argument est le premier élément (la tête) et le second le reste de la liste (la queue).

La suite 1, 2, 3 est donc le terme .(1, .(2, .(3, []))). Dessiné comme un arbre, il a la forme d’un peigne : chaque nœud porte un élément à gauche et le reste à droite, jusqu’à la liste vide.

Heureusement, personne n’écrit cela. On utilise la notation allégée : [1, 2, 3], et surtout la barre verticale, qui sépare les premiers éléments du reste. [X|L] désigne une liste de tête X et de queue L. Toutes ces écritures désignent le même terme :

[1, 2, 3]  =  [1 | [2, 3]]  =  [1, 2 | [3]]  =  [1, 2, 3 | []]

Une liste est un peigne : chaque nœud porte une tête à gauche et le reste de la liste à droite. [T | Q] coupe juste sous la racine.

Cette barre, combinée à l’unification, permet de découper une liste sans aucune fonction d’accès :

?- [a, b, c, d] = [T | Q].
T = a, Q = [b, c, d]

?- [a, b, c, d] = [X, Y | Reste].
X = a, Y = b, Reste = [c, d]

?- [a] = [T | Q].
T = a, Q = []

?- [] = [T | Q].
No

La liste vide n’a ni tête ni queue : elle ne s’unifie pas avec [T|Q]. C’est ce qui distingue le cas de base du cas récursif dans tous les prédicats qui suivent.

La définition d’une liste se transcrit d’ailleurs directement :

liste([]).
liste([_|Q]) :- liste(Q).

Appartenance : le prédicat `membre`

Une station fait-elle partie de la ligne ? X appartient à une liste si c’est sa tête, ou s’il appartient à sa queue :

membre(X, [X|_]).
membre(X, [_|Q]) :- membre(X, Q).

Deux clauses, et un prédicat qui sert dans plusieurs modes.

En mode (+, +), il vérifie : ?- ligne_a(L), membre(republique, L). répond Yes.
En mode (-, +), il énumère les éléments : ?- membre(X, [10, 20]). donne X = 10, puis X = 20, puis « No ».
En mode (+, -), il génère des listes qui contiennent l’élément : ?- membre(10, L). donne L = [10|_], puis L = [_, 10|_], puis L = [_, _, 10|_]… une infinité de réponses.

Remarquez que membre(20, [10, 20, 30, 20, 40]) réussit deux fois, une par occurrence de 20 : l’arbre de recherche a deux feuilles de succès. Ce détail compte quand membre est utilisé au milieu d’un programme : chaque occurrence relancera la suite. La plupart des systèmes fournissent ce prédicat sous le nom member/2.

La clause 1 teste la tête, la clause 2 relance sur la queue : 20 est trouvé deux fois, donc membre réussit deux fois.

Longueur : deux façons de compter

Quelle est la longueur d’une liste ? Celle de sa queue, plus un :

% longueur(+L, ?N)
longueur([], 0).
longueur([_|Q], N) :- longueur(Q, NQ), N is NQ + 1.

Cette version marche, mais observez son déroulement pour une liste de 8 stations : Prolog descend jusqu’à la liste vide en empilant 8 additions en attente, puis les effectue en remontant. Chaque appel doit garder en mémoire le calcul qui reste à faire après lui.

On peut compter en descendant, avec un argument supplémentaire qui porte le résultat partiel : l’accumulateur.

longueur(L, N) :- longueur(L, 0, N).       % on démarre le compte à 0

% longueur(+L, +Acc, ?N) : N = Acc + longueur de L
longueur([], Acc, Acc).                    % liste finie : le compte est le résultat
longueur([_|Q], Acc, N) :-
    Acc1 is Acc + 1,
    longueur(Q, Acc1, N).

L’appel récursif est maintenant le dernier but de la clause : on parle de récursion terminale. Prolog peut alors libérer la mémoire de l’appel courant avant de faire l’appel suivant, exactement comme une boucle. Notez aussi que longueur/2 et longueur/3 sont deux prédicats distincts : c’est une convention courante de nommer l’auxiliaire comme le prédicat principal, avec un argument de plus. Le prédicat prédéfini s’appelle length/2.

Sans accumulateur, chaque appel garde une addition en attente jusqu'à la remontée. Avec, le compte avance en descendant et rien n'attend : c'est une boucle.

Concaténer, découper, retourner

La concaténation

Pour mettre deux listes bout à bout, on ne peut pas écrire [L1|L2] : avec L1 = [1, 2, 3] et L2 = [4, 5], on obtiendrait [[1, 2, 3], 4, 5], une liste dont le premier élément est une liste. Il faut recopier les éléments de la première devant la seconde :

% concat(L1, L2, L3) : L3 est L1 suivie de L2
concat([], L2, L2).
concat([X|R], L2, [X|L3]) :- concat(R, L2, L3).

Ce prédicat (souvent appelé append/3) est bien plus qu’une concaténation, grâce à l’unification. En mode (-, -, +), il découpe une liste de toutes les façons possibles :

?- concat(X, Y, [a, b, c]).
X = [], Y = [a, b, c] ;
X = [a], Y = [b, c] ;
X = [a, b], Y = [c] ;
X = [a, b, c], Y = [] ;
No

En mode (−, −, +), concat essaie chaque point de coupe, de gauche à droite : quatre solutions pour une liste de trois éléments.

Et avec un motif dans le troisième argument, il cherche un élément et sépare ce qui est avant et après :

?- ligne_a(L), concat(Avant, [republique | Apres], L).
Avant = [j_f_kennedy, villejean_universite, pontchaillou, anatole_france, sainte_anne],
Apres = [charles_de_gaulle, gares]

Le dernier élément d’une liste s’obtient de la même façon : dernier(X, L) :- concat(_, [X], L).

Deux façons de construire une liste

Construisons maintenant de nouvelles listes. Un bus express ne s’arrête qu’une station sur deux : on veut les éléments de rang impair.

% elem_impair(+L, -R) : R contient les éléments de rang 1, 3, 5...
elem_impair([], []).
elem_impair([X], [X]).
elem_impair([X, _|Q], [X|R]) :- elem_impair(Q, R).

Sur la ligne a, on obtient [j_f_kennedy, pontchaillou, sainte_anne, charles_de_gaulle]. Ici le résultat est construit dans la tête de la clause : [X|R] est posé tout de suite, et l’appel récursif remplit R. On parle de construction directe ou descendante : les éléments du résultat sont dans le même ordre que ceux de la liste de départ.

Pour le trajet retour, il faut inverser la liste. On pourrait retourner la queue puis concaténer la tête à la fin, mais chaque concaténation reparcourt tout le résultat : le coût devient quadratique. La bonne solution utilise un accumulateur, dans lequel on empile les éléments un par un, comme on retourne une pile d’assiettes :

renverser(L, R) :- renverser(L, [], R).

% renverser(+L, +Acc, -R) : R est L inversée, suivie de Acc
renverser([], Acc, Acc).
renverser([X|Q], Acc, R) :- renverser(Q, [X|Acc], R).

Pour [1, 2, 3], l’accumulateur passe par [], [1], [2, 1], [3, 2, 1], puis la première clause le transmet au résultat. Cette construction est dite ascendante : le résultat reste inconnu pendant toute la descente, les éléments se retrouvent en ordre inverse, et le résultat n’est rendu qu’à la fin, par la clause d’arrêt (on parle de passage final de paramètre). Le coût est linéaire.

Chaque tête de L est empilée en tête de l'accumulateur, comme une pile d'assiettes : l'ordre s'inverse, et la clause d'arrêt rend R = [3, 2, 1].

Construction	Où se construit le résultat	Ordre des éléments	Exemple
Directe (descendante)	dans la tête de la clause récursive	même ordre	`elem_impair`, `concat`
Avec accumulateur (ascendante)	dans un argument supplémentaire, dans le corps	ordre inverse	`renverser`, `longueur/3`

Accéder au énième élément

Pour trouver la N-ième station, on descend dans la liste en décomptant :

% nieme(+N, +L, ?X) : X est le N-ième élément de L (en comptant à partir de 1)
nieme(1, [X|_], X).
nieme(N, [_|Q], X) :-
    N > 1,
    N1 is N - 1,
    nieme(N1, Q, X).

?- ligne_a(L), nieme(3, L, X). donne X = pontchaillou. La garde N > 1 empêche la seconde clause de s’appliquer quand N vaut 1, ce qui ferait continuer la recherche vers 0, −1… inutilement. Ce prédicat ne marche qu’avec N connu : c’est le prix de is.

En résumé

Une liste est [] ou [T|Q] ; [1, 2, 3] n’est qu’une écriture de [1|[2|[3|[]]]], un arbre en forme de peigne.
L’unification avec des motifs comme [X, Y|Reste] remplace toutes les fonctions d’accès.
membre vérifie et énumère ; en mode (+, -), il génère une infinité de listes.
concat concatène, mais aussi découpe une liste de toutes les façons ou isole un élément.
La construction directe place le résultat dans la tête (même ordre) ; la construction avec accumulateur le construit dans le corps (ordre inverse, rendu à la fin).
L’accumulateur donne une récursion terminale : longueur/3 et renverser/3 sont linéaires et économes en mémoire.

Exercices

Exercice · Unifier des listes

facile

Donnez le plus général unificateur, s’il existe :

[a, b, c, d] et [Y|Z]
concat([a, b], [c, d], L) et concat([X|X1], Y, [X|Z])
p([a, b], [c], [Y, Z|T]) et p(A, B, [A|B])
[X, X|_] et [a, b, c]

Voir la solution

Y = a, Z = [b, c, d].
Le premier argument donne X = a, X1 = [b] ; le deuxième, Y = [c, d] ; le troisième, L = [a|Z]. Le pgu est X = a, X1 = [b], Y = [c, d], L = [a|Z] : Z reste libre.
A = [a, b] et B = [c]. Le troisième argument devient [Y, Z|T] = [[a, b]|[c]], c’est-à-dire [[a, b], c]. Donc Y = [a, b] (une liste !), Z = c et T = [].
Pas d’unificateur : le premier élément impose X = a, le second X = b.

En code

?- [a, b, c, d] = [Y|Z].
% Y = a, Z = [b, c, d]

?- concat([a, b], [c, d], L) = concat([X|X1], Y, [X|Z]).
% X = a, X1 = [b], Y = [c, d], L = [a|Z]

?- p([a, b], [c], [Y, Z|T]) = p(A, B, [A|B]).
% A = [a, b], B = [c], Y = [a, b], Z = c, T = []

?- [X, X|_] = [a, b, c].
% No

# Une liste Prolog est un terme : [H|T] = (".", H, T), et [] = "[]"
def L(*elts, queue="[]"):
    for e in reversed(elts):
        queue = (".", e, queue)
    return queue

def est_var(t): return isinstance(t, str) and (t[0].isupper() or t[0] == "_")

def valeur(t, s):                       # applique la substitution
    while est_var(t) and t in s:
        t = s[t]
    return (t[0], *(valeur(a, s) for a in t[1:])) if isinstance(t, tuple) else t

def unifier(a, b, s):
    a, b = valeur(a, s), valeur(b, s)
    if a == b: return s
    if est_var(a): return {**s, a: b}
    if est_var(b): return {**s, b: a}
    if isinstance(a, tuple) and isinstance(b, tuple) and len(a) == len(b) and a[0] == b[0]:
        for x, y in zip(a[1:], b[1:]):
            if (s := unifier(x, y, s)) is None: return None
        return s
    return None

def ecrire(t):                          # affichage à la Prolog : [a, b|Z]
    if isinstance(t, tuple) and t[0] == ".":
        elts = []
        while isinstance(t, tuple) and t[0] == ".":
            elts.append(ecrire(t[1])); t = t[2]
        return "[" + ", ".join(elts) + ("" if t == "[]" else "|" + t) + "]"
    return t

paires = [(L("a", "b", "c", "d"), L("Y", queue="Z")),
          (("concat", L("a", "b"), L("c", "d"), "L"), ("concat", L("X", queue="X1"), "Y", L("X", queue="Z"))),
          (("p", L("a", "b"), L("c"), L("Y", "Z", queue="T")), ("p", "A", "B", L("A", queue="B"))),
          (L("X", "X", queue="_"), L("a", "b", "c"))]
for a, b in paires:
    s = unifier(a, b, {})
    print("échec" if s is None else {v: ecrire(valeur(v, s)) for v in sorted(s) if v != "_"})
# Y = a, Z = [b, c, d]
# L = [a|Z], X = a, X1 = [b], Y = [c, d]
# A = [a, b], B = [c], T = [], Y = [a, b], Z = c
# échec

# Une liste Prolog est un terme : [H|T] = list(".", H, T), et [] = "[]"
L <- function(..., queue = "[]") {
  for (e in rev(list(...))) queue <- list(".", e, queue)
  queue
}
est_var <- function(t) is.character(t) && grepl("^[A-Z_]", t)
valeur <- function(t, s) {                 # applique la substitution
  while (est_var(t) && !is.null(s[[t]])) t <- s[[t]]
  if (is.list(t)) c(t[1], lapply(t[-1], valeur, s = s)) else t
}
unifier <- function(a, b, s) {
  if (is.null(s)) return(NULL)
  a <- valeur(a, s); b <- valeur(b, s)
  if (identical(a, b)) return(s)
  if (est_var(a)) { s[[a]] <- b; return(s) }
  if (est_var(b)) { s[[b]] <- a; return(s) }
  if (is.list(a) && is.list(b) && length(a) == length(b) && identical(a[[1]], b[[1]])) {
    for (i in 2:length(a)) s <- unifier(a[[i]], b[[i]], s)
    return(s)
  }
  NULL
}
ecrire <- function(t) {                    # affichage à la Prolog : [a, b|Z]
  if (!is.list(t)) return(t)
  elts <- c()
  while (is.list(t)) { elts <- c(elts, ecrire(t[[2]])); t <- t[[3]] }
  paste0("[", paste(elts, collapse = ", "), if (t == "[]") "" else paste0("|", t), "]")
}
paires <- list(
  list(L("a", "b", "c", "d"), L("Y", queue = "Z")),
  list(list("concat", L("a", "b"), L("c", "d"), "L"),
       list("concat", L("X", queue = "X1"), "Y", L("X", queue = "Z"))),
  list(list("p", L("a", "b"), L("c"), L("Y", "Z", queue = "T")),
       list("p", "A", "B", L("A", queue = "B"))),
  list(L("X", "X", queue = "_"), L("a", "b", "c")))
for (p in paires) {
  s <- unifier(p[[1]], p[[2]], list())
  v <- sort(setdiff(names(s), "_"))
  cat(if (is.null(s)) "échec" else paste(v, sapply(v, function(x) ecrire(valeur(x, s))),
                                         sep = " = ", collapse = ", "), "\n")
}
# Y = a, Z = [b, c, d]
# L = [a|Z], X = a, X1 = [b], Y = [c, d]
# A = [a, b], B = [c], T = [], Y = [a, b], Z = c
# échec

Exercice · Listes triées et fusion

moyen

Écrivez est_triee(+L), vrai si la liste d’entiers L est triée en ordre croissant (au sens large). [] et [1, 1, 1] sont triées, [3, 2] ne l’est pas.
Écrivez fusion(+L1, +L2, -L3), qui fusionne deux listes triées en une liste triée, en temps linéaire. Par exemple, fusion([4, 10, 20], [1, 11, 15], L) donne L = [1, 4, 10, 11, 15, 20].

Voir la solution

On compare les deux premiers éléments, puis on continue avec la queue en gardant le second (onglet Prolog ci-dessous).
On compare les deux têtes et on place la plus petite en tête du résultat (construction directe).

La deuxième clause s’écrit fusion([X|Q], [], [X|Q]) plutôt que fusion(L, [], L) : sinon, pour deux listes vides, les deux premières clauses s’appliqueraient et la réponse sortirait deux fois. Chaque appel récursif retire un élément de L1 ou de L2 : le nombre d’appels est la somme des longueurs, d’où le coût linéaire.

En code

est_triee([]).
est_triee([_]).
est_triee([X, Y|Q]) :- X =< Y, est_triee([Y|Q]).

fusion([], L, L).
fusion([X|Q], [], [X|Q]).
fusion([X|Q1], [Y|Q2], [X|R]) :- X =< Y, fusion(Q1, [Y|Q2], R).
fusion([X|Q1], [Y|Q2], [Y|R]) :- X > Y, fusion([X|Q1], Q2, R).

% ?- est_triee([1, 1, 1]).                    Yes
% ?- est_triee([3, 2]).                       No
% ?- fusion([4, 10, 20], [1, 11, 15], L).     L = [1, 4, 10, 11, 15, 20]

def est_triee(l):
    """est_triee([X, Y|Q]) :- X =< Y, est_triee([Y|Q])."""
    if len(l) < 2:                      # [] et [_]
        return True
    return l[0] <= l[1] and est_triee(l[1:])   # on garde le second élément

def fusion(l1, l2):
    if not l1: return l2                # fusion([], L, L)
    if not l2: return l1                # fusion([X|Q], [], [X|Q])
    if l1[0] <= l2[0]:
        return [l1[0]] + fusion(l1[1:], l2)
    return [l2[0]] + fusion(l1, l2[1:])

print(est_triee([]), est_triee([1, 1, 1]), est_triee([3, 2]))   # True True False
print(fusion([4, 10, 20], [1, 11, 15]))                       # [1, 4, 10, 11, 15, 20]

est_triee <- function(l) {             # est_triee([X, Y|Q]) :- X =< Y, est_triee([Y|Q]).
  if (length(l) < 2) return(TRUE)      # [] et [_]
  l[1] <= l[2] && est_triee(l[-1])     # on garde le second élément
}
fusion <- function(l1, l2) {
  if (length(l1) == 0) return(l2)      # fusion([], L, L)
  if (length(l2) == 0) return(l1)      # fusion([X|Q], [], [X|Q])
  if (l1[1] <= l2[1]) c(l1[1], fusion(l1[-1], l2)) else c(l2[1], fusion(l1, l2[-1]))
}
c(est_triee(c()), est_triee(c(1, 1, 1)), est_triee(c(3, 2)))   # TRUE TRUE FALSE
fusion(c(4, 10, 20), c(1, 11, 15))                            # 1 4 10 11 15 20

Exercice · Un itinéraire sans boucle

difficile

On reprend le réseau du chapitre 4, en ajoutant un retour liaison(paris, rennes). qui crée un cycle. Le prédicat chemin/2 peut alors tourner indéfiniment.

Écrivez itineraire(+X, +Y, -I), où I est la liste des villes traversées de X à Y (extrémités comprises), sans passer deux fois par la même ville. On pourra écrire un prédicat auxiliaire chemin_sur(X, Y, Vus, I) qui mémorise dans Vus les villes déjà visitées, et un prédicat hors(X, L) vrai si X n’est pas dans la liste L (utilisez \=, qui réussit si deux termes ne sont pas unifiables).

Quelles réponses obtient-on pour itineraire(rennes, paris, I) et itineraire(paris, saint_malo, I) ?

Voir la solution

Vus est un accumulateur : les villes y sont empilées en ordre inverse, et on le retourne une fois arrivé. Le test hors(Z, Vus) interdit de revenir sur une ville déjà visitée. Comme chaque appel ajoute une ville nouvelle et que le réseau est fini, la recherche termine toujours, même avec des cycles.

itineraire(rennes, paris, I) donne I = [rennes, laval, le_mans, paris], puis I = [rennes, vannes, nantes, angers, le_mans, paris], puis « No ».
itineraire(paris, saint_malo, I) donne I = [paris, rennes, saint_malo] : le cycle est utilisé une fois, sans boucler.

Le test hors n’utilise \= que sur des villes connues : nous verrons au chapitre 8 pourquoi les tests « négatifs » doivent toujours porter sur des termes instanciés.

En code

hors(_, []).
hors(X, [Y|Q]) :- X \= Y, hors(X, Q).

itineraire(X, Y, I) :- chemin_sur(X, Y, [X], I).

% chemin_sur(+X, +Y, +Vus, -I) : Vus contient les villes visitées, la plus récente en tête
chemin_sur(X, Y, Vus, I) :-
    liaison(X, Y),
    renverser([Y|Vus], I).
chemin_sur(X, Y, Vus, I) :-
    liaison(X, Z),
    hors(Z, Vus),
    chemin_sur(Z, Y, [Z|Vus], I).

% avec liaison(paris, rennes) en plus du réseau du chapitre 4 :
% ?- itineraire(rennes, paris, I).
% I = [rennes, laval, le_mans, paris] ;
% I = [rennes, vannes, nantes, angers, le_mans, paris] ;
% No
% ?- itineraire(paris, saint_malo, I).
% I = [paris, rennes, saint_malo]

liaison = [("rennes", "saint_malo"), ("rennes", "laval"), ("rennes", "vannes"),
           ("laval", "le_mans"), ("le_mans", "paris"), ("vannes", "nantes"),
           ("nantes", "angers"), ("angers", "le_mans"), ("paris", "rennes")]  # cycle

def chemin_sur(x, y, vus):
    """vus : villes visitées, la plus récente en tête (un accumulateur)."""
    for a, b in liaison:                    # clause 1 : liaison directe
        if (a, b) == (x, y):
            yield list(reversed([y] + vus))
    for a, z in liaison:                    # clause 2 : une ville de plus
        if a == x and z not in vus:         # hors(Z, Vus)
            yield from chemin_sur(z, y, [z] + vus)

def itineraire(x, y):
    return list(chemin_sur(x, y, [x]))

print(itineraire("rennes", "paris"))
# [['rennes', 'laval', 'le_mans', 'paris'], ['rennes', 'vannes', 'nantes', 'angers', 'le_mans', 'paris']]
print(itineraire("paris", "saint_malo"))    # [['paris', 'rennes', 'saint_malo']]

liaison <- data.frame(
  de = c("rennes", "rennes", "rennes", "laval", "le_mans", "vannes", "nantes", "angers", "paris"),
  a  = c("saint_malo", "laval", "vannes", "le_mans", "paris", "nantes", "angers", "le_mans", "rennes"))

# vus : villes visitées, la plus récente en tête (un accumulateur)
chemin_sur <- function(x, y, vus) {
  sol <- list()
  if (any(liaison$de == x & liaison$a == y))            # clause 1 : liaison directe
    sol <- list(rev(c(y, vus)))
  for (z in liaison$a[liaison$de == x])                 # clause 2 : une ville de plus
    if (!(z %in% vus))                                  # hors(Z, Vus)
      sol <- c(sol, chemin_sur(z, y, c(z, vus)))
  sol
}
itineraire <- function(x, y) chemin_sur(x, y, x)

itineraire("rennes", "paris")
# rennes laval le_mans paris ; rennes vannes nantes angers le_mans paris
itineraire("paris", "saint_malo")         # paris rennes saint_malo

Manipulez des listes

Une liste, c’est une tête et une queue

Appartenance : le prédicat membre

Longueur : deux façons de compter

Concaténer, découper, retourner

La concaténation

Deux façons de construire une liste

Accéder au énième élément

En résumé

Exercices

Appartenance : le prédicat `membre`