Liste des symboles rencontrés dans ce chapitre:
CHAR= CHAR/= CHAR< CHAR> CHAR<= CHAR>= CHAR-EQUAL CHAR-NOT-EQUAL CHAR-LESSP CHAR-GREATERP CHAR-NOT-GREATERP CHAR-NOT-LESSP \: STRING= STRING/= STRING< STRING> STRING<= STRING>= STRING-EQUAL STRING-NOT-EQUAL STRING-LESSP STRING-GREATERP STRING-NOT-GREATERP STRING-NOT-LESSP CHAR: CHAR-CODE: CODE-CHAR: MAKE-STRING: STRING: ELT: STRING-UPCASE: NSTRING-UPCASE: STRING-DOWNCASE: NSTRING-DOWNCASE: STRING-CAPITALIZE: NSTRING-CAPITALIZE: MAKE-ARRAY: AREF: SVREF: VECTOR-PUSH: VECTOR-POP: VECTOR-PUSH-EXTEND: *PRINT-ARRAY*: array-dimension-limit array-rank-limit COUNT: REMOVE: DELETE: SUBSTITUTE: FIND: FIND-IF: FIND-IF-NOT: POSITION: COUNT-IF COUNT-IF-NOT: POSITION-IF: REMOVE-IF: REMOVE-IF-NOT: REMOVE-DUPLICATES: CONCATENATE: SORT: MERGE: SUBSEQ: FILL: SEARCH: MISMATCH: EVERY: SOME: NOTANY: NOTEVERY: MAP: MAP-INTO: REDUCE: TRACE: UNTRACE:
LES SÉQUENCES.
LES CARACTÈRES:
#\x >> #\x x au format CHAR
#\space >> #\ l'espace
autres: #\ suivi de Tab, Page, Rubout, Linefeed, Return, Backspace, Newline.
COMPARAISON DES CARACTÈRES:
Sensible à la casse: CHAR=, CHAR/=, CHAR<, CHAR>, CHAR<=, CHAR>=
(char= #\A #\a)
NIL
insensible: CHAR-EQUAL, CHAR-NOT-EQUAL, CHAR-LESSP, CHAR-GREATERP, CHAR-NOT-GREATERP, CHAR-NOT-LESSP
(char-equal #\A #\a)
T
(char-lessp #\A #\a)
NIL A vient-il avant ou après a? ...
(char-greaterp #\A #\a)
NIL ni l'un ni l'autre, car les deux caractères sont considérés comme égaux.
Ces deux prédicats sont insensibles à la casse.
CHAINES DE CARACTÈRES:
\: pour afficher les caractères non affichables dans format. (voir format:)
(format t "foo\\bar") >> foo\bar
(format t "\"foobar\"") >> "foobar"
COMPARAISON DES CHAINES DE CARACTÈRES:
sensible: STRING=, STRING/=, STRING<, STRING>, STRING<=, STRING>=
insensible: STRING-EQUAL, STRING-NOT-EQUAL, STRING-LESSP, STRING-GREATERP, STRING-NOT-GREATERP, STRING-NOT-LESSP
ces fonctions admettent des arguments pour spécifier les sous-chaînes: :start1, :end1, :start2, :end2. Les startx sont inclus et endx sont exclus.
(string= "foobarbaz" "quuxbarfoo" :start1 3 :end1 6 :start2 4 :end2 7)
T "bar" string= "bar"
(string/= "lisp" "lissome")
3 renvoie l'index où l'erreur est détectée dans la 1ère chaîne.
(string< "lisp" "lisper")
4
(length "lisp")
4 rend la longueur de la chaîne passée en argument
CHAR: (comme AREF)
(char "arbre" 2)
#\b rend le caractère situé à la position d'index 2 dans le mot (l'index commence à zéro)
Cette fonction est setf-able, comme on le voit sur l'exemple suivant.
C'est à dire qu'elle sert à désigner la place où setf change une valeur.
(setf (char mot2 2) #\u) ;la 3ème lettre de mot2 est modifiée (indice 2)
(format t "~a devient ~a." mot1 mot2)) ;affichage des deux mots
chat devient chut.
NIL
ASCII:
CHAR-CODE:
(char-code #\A)
65 rend le code ASCII du caractère #\A
CODE-CHAR:
(code-char 65)
#\A rend le caractère ayant pour code ASCII 65
Pour trier les lettres d'un mot dans l'ordre ASCII:
(voir plus loin: sort:)
(sort "arbre" #'char<)
"aberr"
Pour afficher une partie de la table ASCII:
(defun table-ASCII (min max)
(do ((i min (1+ i)))
((> i max))
(format t "~a >>> ~a~a" i (code-char i) #\tab)))
(table-ASCII 97 (+ 97 25))
97 >>> a 98 >>> b 99 >>> c 100 >>> d 101 >>> e 102 >>> f 103 >>> g 104 >>> h 105 >>> i 106 >>> j 107 >>> k 108 >>> l 109 >>> m 110 >>> n 111 >>> o 112 >>> p 113 >>> q 114 >>> r 115 >>> s 116 >>> t 117 >>> u 118 >>> v 119 >>> w 120 >>> x 121 >>> y 122 >>> z
NIL
(defun liste-car (mot)
"convertit un mot en liste de caractères."
(loop for i from 0 to (1- (length mot)) collecting (char mot i)))
(liste-car "arbre")
(#\a #\r #\b #\r #\e)
(defun liste-car-ascii (mot)
"convertit un mot en une liste de codes ascii."
(loop for i from 0 to (1- (length mot)) collecting (char-code (char mot i))))
(liste-car-ascii "arbre")
(97 114 98 114 101)
(defun convert-texte->ascii (phrase)
"convertit une phrase en une liste de codes ascii."
(loop for i from 0 to (1- (length phrase)) collect (char-code (char phrase i))))
(convert-texte->ascii "voici une phrase.")
(118 111 105 99 105 32 117 110 101 32 112 104 114 97 115 101 46)
(make-string 5 :initial-element #\a)
"aaaaa" rend une chaine de caractères de longueur 5 dont les caractères sont initialisés avec l'élément a
STRING:
(string 'symbole)
"SYMBOLE" transforme un symbole en chaîne de caractères
(string #\Z)
"Z" transforme un caractère (au format caractère, donc) en chaîne de caractères d'un caractère
Autre exemple:
(string #\Newline)
"
" Un Newline au format caractère transformé en Newline au format chaîne de caractères.
ELT: (voir également vecteurs ou tableaux: plus loin)
(defparameter ch "chaîne")
CH pour ce qui suit
(elt ch 2)
#\a rend le 3ème caractère de la chaîne ch
STRING-UPCASE:
NSTRING-UPCASE: (avec effet de bord)
(string-upcase "chapitre" :start 2 :end 5)
"chAPItre"
STRING-DOWNCASE:
NSTRING-DOWNCASE: (avec effet de bord)
(string-downcase "CHAPITRE" :start 2 :end 5)
"CHapiTRE"
STRING-CAPITALIZE:
NSTRING-CAPITALIZE:
(defparameter salut "bonjour")
SALUT définition d'une variable contenant la chaine "bonjour"
(string-capitalize salut)
"Bonjour" rend la chaine avec la première lettre en majuscule
salut
"bonjour" la variable salut n'a pas changé
(nstring-capitalize salut)
"Bonjour" NSTRING-CAPITALIZE met aussi la première lettre en capitale, mais...
salut
"Bonjour" ...la variable salut a changé
(string-capitalize "bonjour" :start 3 :end 5)
"bonJour"
Seul j est rendu en majuscule (pas o)
VECTEURS ou TABLEAUX:
MAKE-ARRAY:
(make-array 5 :initial-element nil)
#(NIL NIL NIL NIL NIL)
un vecteur est un tableau à une dimension dont les 5 éléments sont initialisés à NIL
(defparameter vect (make-array 5 :initial-element nil))
VECT construit un vecteur de 5 éléments initialisés par NIL
(make-array '(2 3) :initial-element nil)
#2A((NIL NIL NIL) (NIL NIL NIL))
rend un tableau de dimension 2 (la longueur de la liste passée en argument)
la première dimension a pour taille 2
la deuxième dimension a pour taille 3
(aref tab 2)
NIL le 3ème élément est bien NIL
(setf (aref tab 2) t)
T le 3ème élément devient T
(aref tab 2)
T vérification
tab
#(NIL NIL T NIL NIL) autre vérification
On peut, aussi, utiliser le mot vector:
(vector "a" 1 'd)
#("a" 1 D)
(defparameter vect (vector "a" 1 'd))
VECT pour lui donner un nom
(aref vect 0)
"a" rend la valeur à la position 0
ou mieux:
SVREF: (sv signifie simple vecteur)
(svref vect 1)
1 rend la valeur à la position 1
(make-array 5 :fill-pointer 0)
#() un vecteur de dimension 5 avec un pointeur (de remplissage) initialisé à 0
(defparameter *x* (make-array 5 :fill-pointer 0))
*x* ici le vecteur est nommé pour utilisation ultérieure
VECTOR-PUSH:
(vector-push 'a *x*)
0 place la valeur a à la position pointée en rendant cette position
le pointeur est alors incrémenté
*x*
#(A) le vecteur contient bien A
(vector-push 'b *x*)
1 rend NIL si l'index a déjà atteint 4
*x*
#(A B)
VECTOR-POP:
(vector-pop *x*)
B rend l'item le plus récent en décrémentant le pointeur
*x*
#(A) l'item B n'est plus dans le vecteur
(make-array 5 :fill-pointer 0 :adjustable t)
permet de réajuster la taille la dimension
VECTOR-PUSH-EXTEND:
(vector-push-extend 'b *x*)
rajoute un item même si la dimension est dépassée
(make-array 5 :fill-pointer 0 :adjustable t :element-type 'character)
pour construire des chaînes de caractères lettres par lettres (type character)
(make-array 5 :fill-pointer 0 :adjustable t :element-type 'bit)
pour construire des vecteurs de bit (type bit)
On peut définir un tableau explicitement:
(defparameter tab #2a((a nil b) (c d nil)))
TAB La dimension est précisée après le # (2 ici)
la taille de la première dimension est 2
la taille de la deuxième dimension est 3
(aref tab 0 0)
A rend l'élément d'indices (0,0)
*PRINT-ARRAY*:
tab
#<(SIMPLE-ARRAY T (2 3)) {B6E5417}>
présentation peu explicite quand la variable globale *print-array* est NIL.
(setf *print-array* t)
T *print-array* est mis à T
tab
#2A((A NIL B) (C D NIL)) présentation plus explicite
2 est le nombre de dimensions
Voici deux variables globales:
array-dimension-limit
4611686018427387901
c'est la taille maximale d'une dimension d'un tableau
array-rank-limit
65529 c'est le nombre maximal de dimensions d'un tableau
FONCTIONS SUR LES TYPES SEQUENCE:
Les vecteurs et listes sont des sous-types du type sequence.
(length *x*)
2 rend la longueur du vecteur (ici *x* vaut #(A B))
ELT:
(elt *x* 0)
A rend l'élément de rang 0
(elt *x* 2)
ERROR il n'y a pas d'élément de rang 2
(setf (elt *x* 1) 'c)
C (elt *x* 1) indique, ici, la place où l'on change la valeur
Des fonctions construites sur des itérations:
COUNT:
(count 1 #(1 2 1 2 3 1 2 3 4))
3 rend le nombre de fois que 1 a été trouvé dans le vecteur
REMOVE:
DELETE:
REMOVE et DELETE supprime toutes les occurences du 1er argument (atom) dans le 2ème argument (séquence: liste, vecteur ou chaîne).
REMOVE ne détruit pas la séquence, tandis que DELETE peut la détruire (la transformer).
#(2 2 3 2 3 4) le vecteur ne contient plus l'élément 1 (non destructeur)
(delete 2 #(1 2 1 2 3 1 2 3 4))
#(1 1 3 1 3 4)
(remove 1 '(1 2 1 2 3 1 2 3 4))
(2 2 3 2 3 4) La liste ne contient plus l'élément 1
(delete 2 '(1 2 1 2 3 1 2 3 4))
(1 1 3 1 3 4)
(remove #\a "foobarbaz")
"foobrbz" les a ont été supprimés de la chaîne
(delete #\b "foobarbaz")
"fooaraz"
(defparameter l3 '(1 2 1 2 3 1 (2 3 4)))
L3 définit L3 pour ce qui suit:
(remove 1 l3)
(2 2 3 (2 3 4)) les 1 ont été supprimés
l3
(1 2 1 2 3 1 (2 3 4)) L3 n'est pas modifiée (REMOVE n'est pas destructeur)
(delete 1 l3)
(2 2 3 (2 3 4)) là aussi, les 1 sont supprimés
l3
(1 2 2 3 (2 3 4)) L3 est modifié (DELETE est destructeur)
Remarques:
On ne peut pas supprimer la sous-liste (2 3 4) de L3.
Si on veut supprimer 2 de L3, le 2 de la sous-liste (2 3 4) n'est pas supprimé.
(substitute 9 1 #(1 2 1 2 3 1))
#(9 2 9 2 3 9) substitut 9 à 1
FIND:
syntaxe: find item sequence &key from-end test test-not start end key => element
(Dans slime-repl, placez le curseur sur find et tapez Ctrl+c Ctrl+d h,
ceci vous mène dans Common Lisp HyperSpec pour plus de renseignements sur la syntaxe.)
(find 2 '(1 2 1 2 3 1 2 3 4))
2 renvoie la valeur trouvée, sinon NIL
FIND-IF:
syntaxe: find-if predicate sequence &key from-end start end key => element
FIND-IF-NOT:
syntaxe: find-if-not predicate sequence &key from-end start end key => element
(find-if #'evenp '(1 2 1 2 3 1 2 3 4))
2 renvoie le 1er nombre pair trouvé
(find-if #'oddp '(1 2 1 2 3 1 2 3 4) :from-end t)
3
renvoie le 1er nombre impair trouvé en partant de la fin de la liste
(find-if #'oddp '(1 2 1 2 3 1 2 3 4) :end 7 :from-end t)
1
renvoie le 1er nombre impair trouvé avant l'index 7 et en partant de la fin
précisons: l'index 7 correspond à 3, avant c'est 2 (pair), et avant 2 c'est 1 qui est bien impair
(find-if #'oddp '(1 2 3 4 5 6 7 8 9) :end 7 :from-end t)
7
pour confirmer ce qui vient d'être dit
2 renvoie le 1er nombre non-impair trouvé
POSITION:
(position 2 '(1 2 1 2 3 1 2 3 4))
1 renvoie l'index du premier 2 trouvé dans la liste, sinon NIL
(position #\b "foobarbaz")
3 renvoie l'index du premier b trouvé dans la chaîne, sinon NIL
REMOVE et SUBSTITUTE renvoient des séquences de même type que l'argument.
Le comportement de ces fonctions peut être modifié par l'utilisation de mots-clés en argument.
(count "foo" #("foo" "bar" "baz") :test #'string=)
1 le comparateur par défaut est EQL, remplacé, ici, par string=
(find 'a #((a 10) (b 20) (a 30) (b 40)) :key #'first)
(A 10)
mais:
(find 'a #((a 10) (b 20) (a 30) (b 40)) :key #'first :from-end t)
(A 30)
(remove #\a "foobarbaz" :count 1)
"foobrbaz" supprime le 1er a à partir de la gauche
(remove #\a "foobarbaz" :count 2)
"foobrbz" supprime tous les a jusqu'au 2ème
(remove #\a "foobarbaz" :count 1 :from-end t)
"foobarbz" supprime le 1er a à partir de la droite
(position 'c '((a b) (c d) (e f)) :key #'car)
1 rend la position de l'élément commençant par a
(position 4 '(2 0 6 4) :test #'<)
2 rend la position d'un élément pour lequel 4 est plus petit que cet élément
Il peut y avoir des effets de bord si :from-end ne change pas le résultat de la fonction count. L'ordre des éléments passés à :test et :key peut changer. Exemple:
(defparameter *v* #((a 10) (b 20) (a 30) (b 40)))
*V*
(defun verbose-first (x) (format t "J'analyse ~s~%" x) (first x))
VERBOSE-FIRST
(count 'a *v* :key #'verbose-first)
J'analyse (A 10)
J'analyse (B 20)
J'analyse (A 30)
J'analyse (B 40)
2
(count 'a *v* :key #'verbose-first :from-end t)
J'analyse (B 40)
J'analyse (A 30)
J'analyse (B 20)
J'analyse (A 10)
2
RESUME SUR LES MOTS-CLES:
:test utilise deux arguments de la fonction concernée et compare la valeur passée en argument à l'item ou à la valeur extraite par :key (la valeur par défaut donnée à :test est EQL)
:key utilise un argument de la fonction pour en extraire la valeur-clé. Si NIL, l'élément est utilisé tel qu'il est (par défault :key est NIL)
:start utilise le numéro d'index de début (inclusif) d'une sous-séquence (valeur par défaut 0)
:end utilise le numéro d'index de fin (exclusif) d'une sous-séquence. NIL indique la fin de la séquence (valeur par défaut NIL)
:from-end si ce mot-clé a pour valeur T, la séquence est analysée de la fin vers le début (valeur par défaut NIL)
:count indique le nombre d'éléments à effacer ou à substituer. Si NIL, tout est effacé ou remplacé (valeur par défaut NIL)
FONCTIONS VARIANTES DE HAUT NIVEAU:
COUNT-IF
(count-if #'evenp #(1 2 3 4 5))
2 rend le nombre de nombres pairs
COUNT-IF-NOT:
(count-if-not #'evenp #(1 2 3 4 5))
3 rend le nombre de nombres non pairs
POSITION-IF:
(position-if #'digit-char-p "abcd00O1")
4 rend la valeur d'index de la chaîne de caractères où se trouve la première valeur numérique
REMOVE-IF:
(remove-if #'oddp '(1 2 3 4 5))
(2 4) supprime de la liste les nombres impairs
REMOVE-IF-NOT:
(remove-if-not #'(lambda (x) (char= (elt x 0) #\f)) #("foo" "bar" "baz" "foom"))
#("foo" "foom") supprime les éléments qui ne commencent pas par f
Ces variantes admettent les même mots-clés sauf :test car l'argument principal est déjà une fonction:
(count-if #'evenp #((1 a) (2 b) (3 c) (4 d) (5 e)) :key #'first)
2 rend le nombre de listes dont le premier élément est pair
(count-if-not #'evenp #((1 a) (2 b) (3 c) (4 d) (5 e)) :key #'first)
3 rend le nombre de listes dont le premier élément n'est pas pair
(remove-if-not #'alpha-char-p #("foo" "bar" "1baz") :key #'(lambda (x) (elt x 0)))
#("foo" "bar") rend la liste des éléments qui ne commencent pas par un nombre
La famille REMOVE possède une quatrième variante:
REMOVE-DUPLICATES:
(remove-duplicates #(1 2 1 2 3 1 2 3 4))
#(1 2 3 4) rend un vecteur d'éléments en supprimant les éléments dupliqués
Le vecteur initial est conservé (non destructeur)
REMOVE-DUPLICATES prend les mêmes mots-clés en argument, sauf :count
(remove-duplicates '("abc" "def" "abc" "ghi" "def"))
("abc" "def" "abc" "ghi" "def") les chaînes ne sont pas EQL: les pointeurs sont différents
(remove-duplicates '("abc" "def" "abc" "ghi" "def") :test #'equal)
("abc" "ghi" "def") les chaînes sont bien EQUAL
TOUTES LES MANIPULATIONS DE SEQUENCE:
CONCATENATE:
(concatenate 'vector #(1 2 3) '(4 5 6))
#(1 2 3 4 5 6) rend un vecteur dont les éléments ont été concaténés
(concatenate 'list #(1 2 3) '(4 5 6))
(1 2 3 4 5 6) rend une liste dont les éléments ont été concaténés
Notez que le 2ème argument est un vecteur et le troisième une liste dans ces deux derniers cas.
Mais on peut mettre deux ou plusieurs listes à suivre:
(concatenate 'list '(1 2) '(3 4) '(5 6))
(1 2 3 4 5 6)
(concatenate 'string "abc" '(#\d #\e #\f))
"abcdef" rend une chaîne de caractères dont les éléments ont été concaténés
On peut concaténer plusieurs chaînes:
(concatenate 'string "abc" "def" "ghi")
"abcdefghi"
Il faut noter la nécessité d'indiquer le type désiré en 1er argument.
Une chaîne peut-être transformée en liste ou en vecteur avec des éléments de type CHARACTER.
(voir la fonction liste-car plus haut)
L'inverse n'est possible que si les éléments sont du type CHARACTER.
TRI:
SORT:
(sort (vector "foo" "bar" "baz") #'string<)
#("bar" "baz" "foo") mots rangés dans l'ordre alphabétique dans un vecteur
(sort (list "foo" "bar" "baz") #'string<)
("bar" "baz" "foo") mots rangés dans l'ordre alphabétique dans une liste
(sort (remove-duplicates "arbre") #'string<)
"aber" rend les lettres du mot arbre dans l'ordre alphabétique sans duplication. REMOVE-DUPLICATES supprime toute duplication de lettre
A la place de SORT on peut utiliser STABLE-SORT.
Ces deux fonctions sont destructives, ce qui veut dire, d'une part, qu'il faut savoir quoi faire de la séquence retournée par la fonction, d'autre part, qu'il vaut mieux passer une copie de la séquence à ces fonctions, à moins qu'on en ait fini avec cette séquence. Prévoir, donc, quelquechose de la forme:
(setf ma-séquence (sort ma-séquence #'string<))
ce que rend SORT est placé dans ma-séquence dont le contenu initial a été détruit par SORT ou même (tout dépend de ce que l'on veut obtenir):
(setf néo-séquence (sort (copy-seq ma-séquence) #'string<))
l'ancien contenu de ma-séquence est conservé, puisque SORT travaille sur une copie. le résultat est placé dans néo-séquence
(sort '(4 1 2 3) #'<)
(1 2 3 4) rend la liste des nombres rangés dans l'ordre croissant
(sort '(4 1 2 3) #'>)
(4 3 2 1) rend la liste des nombres rangés dans l'ordre décroissant
TRI et FUSION:
MERGE:
(merge 'vector #(1 3 5) #(2 4 6) #'<)
#(1 2 3 4 5 6) fusionne les deux séquences en ordonnant les éléments selon la fonction de comparaison. Le premier argument indique le type du résultat.
(merge 'list #(1 3 5) #(2 4 6) #'<)
(1 2 3 4 5 6) ici, on obtient une liste
On peut trier une liste de nombres en utilisant les deux fonctions suivantes:
Pour placer un élément dans une liste déjà triée:
(defun ins (X L)
"Insère X au bon endroit dans une liste déjà triée"
(cond ((null L) (list X))
((< X (car L)) (cons X L)) ;"<" impose un ordre croissant
(t (cons (car L) (ins X (cdr L))))
))
Pour trier une liste de nombres: cette fonction fait appel à la précédente.
(defun tri (L)
"trie une liste de nombres dans l'ordre déterminée par la fonction INS."
(cond ((null L) nil)
(t (ins (car L) (tri (cdr L))))
))
(tri '(1 4 7 2 5 8 3 6 9))
(1 2 3 4 5 6 7 8 9)
Comme c'est un peu gênant d'avoir une fonction ins qui impose un ordre de tri,
on peut faire appel à un argument optionnel de la fonction TRI, qui contiendra #'< par défaut.
Par contre, l'argument devient obligatoire dans la fonction INS.
Voici ces deux fonctions modifiées:
(defun ins (X L p)
"Insère X au bon endroit dans une liste déjà triée"
(cond ((null L) (list X))
((funcall p X (car L)) (cons X L)) ;bien noter le "funcall p"
(t (cons (car L) (ins X (cdr L) p)))))
(defun tri (L &optional (p #'<))
"trie une liste de nombres dans l'ordre précisé."
(cond ((null L) nil)
(t (ins (car L) (tri (cdr L) p) p)))) ;bien noter que p intervient 2 fois sur cette ligne
(tri '(2 8 6 1 3))
(1 2 3 6 8)
(tri '(2 8 6 1 3) #'>)
(8 6 3 2 1)
Trier une liste de sous-listes suivant le 2ème élément de chaque sous-liste:
(sort '((1 3) (1 5) (2 2) (3 4)) (lambda (x y) (< (second x) (second y))))
((2 2) (1 3) (3 4) (1 5))
Manipulation des SOUS-SEQUENCES:
SUBSEQ:
(subseq "foobarbaz" 3)
"barbaz" rend la sous-séquence à partir de l'index 3
(subseq "foobarbaz" 3 6)
"bar" rend la sous-séquence entre l'index 3 compris et l'index 6 non compris
(subseq '("foo" "bar" "baz" "foom") 2)
("baz" "foom") même chose pour une liste
(subseq '("foo" "bar" "baz" "foom") 2 3)
("baz")
la fonction SUBSEQ peut servir à désigner une place dans SETF (la fonction est dite "setf-able"):
(defparameter *x* (list "foo" "bar" "baz" "foom"))
*X* définit la variable *x*
*x*
("foo" "bar" "baz" "foom") ici, avec une liste
(setf (subseq *x* 2 3) '("xxx"))
("xxx") bien noter que SUBSEQ rend une sous-liste et, donc, SETF attend une liste pour remplacer la sous-liste
*x*
("foo" "bar" "xxx" "foom")
(defparameter *y* "foobarbaz")
*Y*
*y*
"foobarbaz" ici, avec une chaîne de caractères
(setf (subseq *y* 3 6) "yyy")
"yyy" notons que la sous-séquence et la nouvelle valeur...
*y*
"fooyyybaz" ...ont la même longueur.
(setf (subseq *y* 3 6) "abcd")
"abcd" la nouvelle valeur est plus longue que la sous-séquence...
*y*
"fooabcbaz" ...la nouvelle valeur a été tronquée
(setf (subseq *y* 3 6) "yy")
"yy" la nouvelle valeur est plus courte que la sous-séquence...
*y*
"fooyycbaz" ...le début de la sous-séquence, seule, est modifiée
(defun palindrome (mot)
"rend le mot si c'est un palindrome, NIL sinon. N'accepte pas les mots de moins de trois lettres."
(if (> (length mot) 2)
(let* ((long (length mot)) (mil (floor (/ long 2))))
(cond
((and (evenp long)
(equal (subseq mot 0 mil)
(reverse (subseq mot mil)))) mot)
((and (oddp long)
(equal (subseq mot 0 mil)
(reverse (subseq mot (+ 1 mil))))) mot)
(t nil)))
nil))
(palindrome "laval")
"laval" laval est bien un palindrome
La fonction palindrome ne vérifie pas si le mot existe bien.
Si on a une liste de mots, en utilisant LOOP, on peut collecter les mots qui sont des palindromes:
(loop for x in '("trop" "à" "où" "ici" "car" "clan" "laval" "rideau" "coloc")
when (palindrome x)
collect x)
("ici" "laval" "coloc")
FILL:
(fill *y* #\x)
"xxxxxxxxx" rempli toute la chaîne avec des x
(fill *y* #\z :start 3 :end 6)
"xxxzzzxxx" rempli de z la sous-chaîne allant de l'index 3 (compris) à l'index 6 (non compris)
SEARCH:
(search "bar" "foobarbaz")
3 recherche la sous-chaîne "bar" dans la chaîne "foobarbaz" et renvoie son index.
(search "bac" "foobarbaz")
NIL renvoie NIL si la sous-chaîne n'est pas trouvée
MISMATCH:
(mismatch "foobarbaz" "foom")
3 rend l'index à partir duquel les deux mots diffèrent
rend NIL, si les mots sont identiques
(mismatch "bac" "foobarbaz" :start1 0 :end1 3 :start2 3 :end2 6)
2 compare "bac" et "bar" et rend l'index de c relatif à la première chaîne
(mismatch "foobarbaz" "bac" :start1 3 :end1 6 :start2 0 :end2 3)
5 rend, ici, l'index de r relatif à la première chaîne
MISMATCH utilise aussi les mots-clés :key, :test, :from-end en arguments:
(mismatch "foobazbar" "bar" :from-end t)
6 rend l'index du 2ième b de "foobazbar"
(mismatch "foobazbar" "bac" :from-end t)
9 la différence est à l'index 8: rend 9.
(mismatch "foobazbar" "car" :from-end t)
7 la différence est à l'index 6: rend 7
Remarque: dans le sens gauche-droite, MISMATCH rend l'index où se trouve la différence.
dans le sens droite-gauche, MISMATCH rend l'index précédent la différence (l'index où se trouve la différence + 1)
EVERY:
SOME:
NOTANY:
NOTEVERY:
A rapprocher du quantificateur 'quelque soit':
(every #'evenp #(1 2 3 4 5))
NIL teste si tous les éléments du vecteur sont pairs
(every #'evenp #(2 4 6 8 10))
T
A rapprocher du quantificateur 'il existe':
(some #'evenp #(1 2 3 4 5))
T teste si, au moins, un élément du vecteur est pair
(some #'evenp #(1 3 5 7 9))
NIL
(notany #'evenp #(1 2 3 4 5))
NIL teste si aucun élément du vecteur est pair
(notany #'evenp #(1 3 5 7 9))
T
(notevery #'evenp #(1 2 3 4 5))
T teste si un élément n'est pas pair
(notevery #'evenp #(2 4 6 8 10))
NIL
(every #'> #(1 2 3 4) #(5 4 3 2))
NIL compare, deux à deux, les éléments des vecteurs. Rend T si tous les tests sont vrais.
(some #'> #(1 2 3 4) #(5 4 3 2))
T compare, deux à deux, les éléments des vecteurs. Rend T si, au moins, un couple vérifie le test.
(notany #'> #(1 2 3 4) #(5 4 3 2))
NIL teste si aucun couple ne vérifie le test.
(notevery #'> #(1 2 3 4) #(5 4 3 2))
T teste si un couple vérifie le test.
MAP:
Les arguments de MAP sont: le type du résultat, une fonction à n arguments et n séquences:
(map 'vector #'* #(1 2 3) #(10 9 8))
#(10 18 24) rend un vecteur contenant les produits, 2 à 2, des éléments
(map 'list #'* #(1 2 3) #(10 9 8))
(10 18 24) rend une liste contenant les produits, 2 à 2, des éléments
(map 'list #'+ #(1 2 3) #(10 9 8) #(4 5 6))
(15 16 17) rend une liste contenant les sommes, 3 à 3, des éléments des 3 vecteurs
MAP-INTO:
(setf v1 (vector 1 2 3))
#(1 2 3) définition d'un vecteur v1
(map-into v1 #'+ v1 #(4 5 6))
#(5 7 9) rend v1, somme de v1 et du vecteur #(4 5 6)
v1
#(5 7 9) v1 a bien changé
(map-into v1 #'+ v1 #(1 2))
#(6 9 9) la somme a été effectuée sur les deux premiers éléments.
le 3ième est inchangé
REDUCE:
Voici la syntaxe de reduce:
reduce function sequence &key key from-end start end initial-value => result
où:
function désigne une fonction qui peut être appelée soit avec zéro argument soit avec deux arguments.
sequence est une séquence propre (voir liste propre)
key désigne une fonction à un argument ou NIL.
from-end est un booléen (false par défaut) qui autorise à prendre la séquence par la fin.
start désigne l'index de début (inclu) de la séquence (0 par défaut).
end désigne l'index de fin (exclu) de la séquence (NIL par défaut)
initial-value s'ajoute à la séquence obtenue au début (ou à la fin si from-end est sollicité), et est pris en compte dans la réduction.
Quelques exemples:
(reduce #'+ #(1 2 3 4 5 6 7 8 9 10))
55 rend la somme des nombres contenus dans le vecteur
(reduce #'+ #(1 2 3 4 5 6 7 8 9 10) :start 1 :end 3)
5 ce qui correspond à 2+3, start donne l'index inclu et end l'index exclu.
(reduce #'* '(1 2 3 4))
24 1x2x3x4
(reduce #'* '(1 2 3 4) :initial-value 5)
120 5x1x2x3x4
(reduce #'/ '(1 2 3 4))
1/24 ((1/2)/3)/4
(reduce #'/ '(1 2 3 4) :from-end t)
3/8 1/(2/(3/4))
(reduce #'+ (map 'vector #'* v1 v1))
198 rend le carré scalaire du vecteur v1
(sqrt (reduce #'+ (map 'vector #'* v1 v1)))
14.071247 rend le module du vecteur v1
(reduce #'max #(5 3 7 2 1))
7 rend le plus grand élément du vecteur
Ce dernier cas montre la puissance de REDUCE, car MAX n'agit que sur une suite de nombres (exemple: (max 3 7 1)), pas sur un vecteur, ni sur une liste.
REDUCE admet, en argument, des mots-clés: :key, :from-end, :start, :end et même :initial-value.
(reduce #'max #(5 3 7 2 1) :initial-value 10)
10 aucun élément ne dépasse 10
(reduce #'max #(5 3 7 2 1) :initial-value 6)
7 la valeur initiale 6 est dépassée
(reduce #'max #(5 3 7 2 1) :start 3 :end 4)
2 rend la valeur maximale entre les index 3 et 4
Application: extraction de mots dans une phrase.
(defun extracteur-mots (phrase début &optional (test #'alpha-char-p)) ;à l'appel début vaut zéro et, par défaut, le test est alpha-char-p
(let ((pointeur1 (position-if test phrase :start début))) ;pointeur1 a la valeur rendue par POSITION-IF
(if pointeur1 ;si vrai
(let ((pointeur2 (position-if #'(lambda (signe) (not (funcall test signe))) phrase :start pointeur1))) ;2ème pointeur
(cons (subseq phrase pointeur1 pointeur2) ;extraction de la sous-séquence
(if pointeur2 ;si vrai
(extracteur-mots phrase pointeur2 test) ;récursion et nouvelle extraction
nil))) ;fin de l'extraction si pointeur2 est NIL
nil))) ;fin de l'extraction si pointeur1 est NIL
(extracteur-mots "Alpha15 6Bêta-g Gamma" 0)
("Alpha" "Bêta" "g" "Gamma") rend la liste des mots formés de caractères alphabétiques
tout autre caractère est pris comme séparateur
(extracteur-mots "Alpha15 6Bêta-g Gamma" 0 #'alphanumericp)
("Alpha15" "6Bêta" "g" "Gamma") rend la liste des mots formés de caractères alpha-numériques
tout autre caractère est pris comme séparateur
(extracteur-mots "Alpha15 6Bêta-g" 0 #'upper-case-p)
("A" "B") rend la liste des lettres majuscules de la phrase
Dans la fonction "extracteur-mots" le test ne se fait qu'avec un seul prédicat.
Si on veut combiner plusieurs tests, il faut les placer dans un container:
(defun contenant-p (signe) ;l'analyse se fera sur chaque signe: donc un seul argument
(and (graphic-char-p signe) ;tous les signes sont admis
(not (char= signe #\space)))) ;sauf le caractère "espace"
(extracteur-mots "Alpha15 6Bêta-g Gamma" 0 #'contenant-p)
("Alpha15" "6Bêta-g" "Gamma") rend tous les signes sauf les espaces sous forme d'une liste de 'mots'
La fonction suivante calcule le nombre d'occurence de chaque caractère dans la chaine passée en argument.
Elle rend le résultat sous la forme d'une liste de doublets (caractère . occurence):
(defun occurence-caractère (chaine)
"rend une alist où chaque clé est un caractère et chaque valeur l'occurence du caractère dans la chaine."
(if (string= "" chaine)
nil
(apply #'list (cons (char chaine 0) (count (char chaine 0) chaine)) (occur (remove (char chaine 0) chaine)))))
OCCURENCE-CARACTÈRE
(occurence-caractère "une grande chaine de caractères.")
((#\u . 1) (#\ . 4) (#\. . 1) (#\a . 4) (#\c . 3) (#\d . 2) (#\e . 5)
(#\g . 1) (#\h . 1) (#\i . 1) (#\n . 3) (#\r . 3) (#\s . 1) (#\t . 1)
(#\LATIN_SMALL_LETTER_E_WITH_GRAVE . 1)) on voit, par exemple, que la lettre e est utilisée 5 fois dans la chaine
Si on veut les résultats dans l'ordre décroissant des occurences, on peut utiliser la fonction tri-doublet déjà vue:
(tri-doublet (occurence-caractère "une grande chaine de caractères."))
((#\e . 5) (#\a . 4) (#\ . 4) (#\r . 3) (#\n . 3) (#\c . 3) (#\d . 2)
(#\LATIN_SMALL_LETTER_E_WITH_GRAVE . 1) (#\t . 1) (#\s . 1) (#\i . 1)
(#\h . 1) (#\g . 1) (#\. . 1) (#\u . 1))
Et dans l'ordre ASCII des clés:
(occurence-caractère (sort "une grande chaine de caractères." #'string<))
((#\ . 4) (#\. . 1) (#\a . 4) (#\c . 3) (#\d . 2) (#\e . 5) (#\g . 1)
(#\h . 1) (#\i . 1) (#\n . 3) (#\r . 3) (#\s . 1) (#\t . 1) (#\u . 1)
(#\LATIN_SMALL_LETTER_E_WITH_GRAVE . 1))
On peut aussi redéfinir les fonctions ins-doublet et tri-doublet:
(defun ins-doublet-clé (x l)
"insère un doublet dans une liste déjà triée."
(if (null l) (list x)
(if (string< (car x) (car (car l)))
(cons x l)
(cons (car l) (ins-doublet-clé x (cdr l))))))
INS-DOUBLET-CLÉ
(defun tri-doublet-clé (l)
"trie une liste de doublets dans l'ordre ASCII des clés."
(if (null l) nil
(ins-doublet-clé (car l) (tri-doublet-clé (cdr l)))))
TRI-DOUBLET-CLÉ
(tri-doublet-clé (occurence-caractère "une grande chaine de caractères."))
((#\ . 4) (#\. . 1) (#\a . 4) (#\c . 3) (#\d . 2) (#\e . 5) (#\g . 1)
(#\h . 1) (#\i . 1) (#\n . 3) (#\r . 3) (#\s . 1) (#\t . 1) (#\u . 1)
(#\LATIN_SMALL_LETTER_E_WITH_GRAVE . 1))
La fonction suivante permet de trier les éléments d'un simple vecteur:
Elle fait intervenir plusieurs macros (when, incf, decf, rotatef).
Sans ces macros la fonction serait difficilement lisible.
(defun vite-trier (vec g d)
(let ((long (length vec))) ;long prend la valeur de la longueur du vecteur
(cond ;conditions sur g et d pour qu'il n'y ait pas d'erreur
((< g 0) (print "le 2ème argument doit être positif ou nul.") nil)
((>= g long) (format t "le 2ème argument doit être plus petit que ~a" long) nil)
((< d g) (print "le 3ème argument doit être plus grand que le 2ème.") nil)
((>= d long) (format t "le 3ème argument doit être plus petit que ~a" long) nil)
(t ;la procédure de tri commence là
(let ((i g) ;i prend la valeur de g
(j d) ;j prend la valeur de d
(p (svref vec (round (+ g d) 2)))) ;p est l'élément pivot situé à une position d'index moyenne entre g et d
(tant-que (<= i j) ;tant que i<=j ...
(tant-que (< (svref vec i) p) (incf i)) ;tant que l'élément à l'index i est plus petit que p, i est incrémenté
(tant-que (> (svref vec j) p) (decf j)) ;tant que l'élément à l'index j est plus grand que p, j est décrémenté
(when (<= i j) ;si on a toujours i<=j ...
(rotatef (svref vec i) (svref vec j)) ;...les éléments d'index i et j sont échangés
(incf i) ;i est incrémenté
(decf j))) ;j est décrémenté
(if (>= (- j g) 1) (vite-trier vec g j)) ;si l'écart entre g et j est supérieur ou égal à 1, on trie entre g et j
(if (>= (- d i) 1) (vite-trier vec i d)))))) ;si l'écart entre d et i est supérieur ou égal à 1, on trie entre i et d
vec) ;sortie d'itération quand j=g et i=d, et le vecteur trié est rendu
Remarque: l'arrondi (round (+ g d) 2) se fait normalement à la valeur entière la plus proche. Comme g et d sont entiers,
l'arrondi se fait sur les valeurs entières paires. Le pivot est choisit en conséquence et cela ne modifie pas le résultat.
Essayons cette fonction en demandant la trace:
(defparameter v (vector 3 2 5 1 4 7 6))
V
TRACE:
(trace vite-trier)
(VITE-TRIER)
(vite-trier v 0 6)
0: (VITE-TRIER #(3 2 5 1 4 7 6) 0 6)
1: (VITE-TRIER #(1 2 5 3 4 7 6) 1 6)
2: (VITE-TRIER #(1 2 4 3 5 7 6) 1 3)
3: (VITE-TRIER #(1 2 3 4 5 7 6) 1 2)
3: VITE-TRIER returned #(1 2 3 4 5 7 6)
2: VITE-TRIER returned #(1 2 3 4 5 7 6)
2: (VITE-TRIER #(1 2 3 4 5 7 6) 4 6)
3: (VITE-TRIER #(1 2 3 4 5 6 7) 4 5)
3: VITE-TRIER returned #(1 2 3 4 5 6 7)
2: VITE-TRIER returned #(1 2 3 4 5 6 7)
1: VITE-TRIER returned #(1 2 3 4 5 6 7)
0: VITE-TRIER returned #(1 2 3 4 5 6 7)
#(1 2 3 4 5 6 7) on voit que la fonction récursive vite-trier est appelée 6 fois
L'appel se fait jusqu'au 3ème niveau sous le "top-level"
UNTRACE:
(untrace vite-trier)
T pour ne plus tracer la fonction vite-trier
prochainement: "TABLES de HACHAGE."
Aucun commentaire:
Enregistrer un commentaire