INF6120 - Laboratoire 8

Les problèmes de ce labo sont inspirés de la suite de problème P-99

Listes

1. Écrire une relation palindrome/1 qui est vraie pour les listes étant un palindromes.

?- palindrome([a,b,c,b,a]).
true.

?- palindrome([a,b,c]).
false.

2. Écrire une relation compress/2 entre une liste et la liste contenant les mêmes éléments, mais avec les éléments identiques consécutifs éliminés.

?- compress([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
X = [a,b,c,a,d,e]

3. Écrire une relation pack/2 entre une liste et la liste contenant les éléments identiques consécutifs groupés en sous-listes.

pack([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
X = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]]

4. Écrire une relation encode/2 entre une liste et son encodage RLE.

?- encode([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
X = [[4,a],[1,b],[2,c],[2,a],[1,d][4,e]]

5. Écrire la relation inverse à encode/2. Astuce : vous avez déjà codé la logique dans encode/2, la définition de decode/2 peut donc se faire en un unique appel à encode/2

?- decode([[4,a],[1,b],[2,c],[2,a],[1,d][4,e]], X).
X = [a,a,a,a,b,c,c,a,a,d,e,e,e,e].

Arbres

1. Écrire un prédicat istree/1 qui est vrai pour les arbres binaires écrit sous la forme t(X, Left, Right) pour un nœud annoté avec X et composé de deux branches Left et Right, et nil pour les feuilles.

?- istree(t(a,t(b,nil,nil),nil)).
true.
?- istree(t(a,t(b,nil,nil))).
false.

2. Écrire une relation count_leaves/2 entre un arbre et son nombre de feuilles.

?- count_leaves(t(a,t(b,nil,nil),nil),N).
N = 3.

3. ÉCrire une relation leaves/2 entre un arbre et la liste des éléments contenus dans ses nœuds.

?- leaves(t(a,t(b,nil,nil),nil),L).
L = [a, b].