Fiche de révision : Listes d’entiers en machine de Peano

📋 Plan du Cours

1. Opérations primitives sur les listes
2. Fonctions renvoyant un entier
3. Fonctions renvoyant une liste
4. Autres fonctions sur les listes

📖 1. Opérations primitives sur les listes

🔑 Notions clés & Définitions

• Liste vide : L’expression [] renvoie la liste vide.
• cons : La fonction cons(X,L) renvoie la liste dont la tête est l’entier X et le reste est la liste L.
• car : La fonction car(L) renvoie la tête de la liste L, mais son résultat est indéterminé si L est vide.
• cdr : La fonction cdr(L) renvoie le reste de la liste L, privée de son premier élément, mais son résultat est indéterminé si L est vide.
• vide : La fonction vide(L) renvoie 1 si L est vide et 0 sinon.

📝 Points essentiels

• Le modèle GRAND LUXE, version 3 de la machine de Peano, ajoute les listes d’entiers et leurs opérations au modèle LUXE.

📖 2. Fonctions renvoyant un entier

🔑 Notions clés & Définitions

• lgr : La fonction lgr(L) renvoie la longueur de L, c’est-à-dire le nombre d’éléments qu’elle contient ; elle renvoie 0 si L est vide et sinon ajoute 1 au résultat de lgr(cdr(L)).
• appartient : La fonction appartient(X,L) renvoie 1 si l’entier X appartient à L et 0 sinon.
• nieme : La fonction nieme(N,L) renvoie l’élément d’indice N de L, dont le premier élément a l’indice 1 ; le résultat est indéterminé si N vaut 0 ou si L contient moins de N éléments.

📖 3. Fonctions renvoyant une liste

🔑 Notions clés & Définitions

• n_a_un : La fonction n_a_un(N) renvoie la liste des entiers de N à 1 inclus, et renvoie la liste vide si N vaut 0.
• renverser : La fonction renverser(L) renvoie la liste contenant les éléments de L dans l’ordre inverse.
• concat : La fonction concat(L,M) renvoie la concaténation de L et M, c’est-à-dire leur mise bout à bout.
• fusion : La fonction fusion(L,M), appliquée à deux listes déjà triées par ordre croissant, renvoie une liste triée contenant tous les éléments de L et de M.

📖 4. Autres fonctions sur les listes

📝 Points essentiels

• Les fonctions proposées pour s’entraîner davantage sont : nb_occ(X,L), qui compte les occurrences de X dans L, dernier(L), qui renvoie le dernier élément, min(L), qui renvoie le plus petit élément, un_a_n(N), qui construit la liste de 1 à N inclus, sup(X,L), qui renvoie les éléments de L supérieurs à X, ajoute_fin(X,L), qui ajoute X à la fin de L