Paradigmes de programmation et Lisp pour IA

Imprimer la valeur trouv e

Une session LISP consiste faire valuer successivement

diff rentes expressions qui ob issent une syntaxe tr s simple.

26

Lalgorithme dex cution

de linterpr te est une

boucle

READ EVAL PRINT

Qui sex cute divers

niveaux de profondeur en

commen ant par le plus

profond

Lecture dune

expression

Evaluation de

lexpression

Impression du

r sultat

27

} LISP ne fait pas une distinction lexicale entre les

symboles de fonctions et les symboles de variables.

} Sinon, ceci va nous emp cher de construire par

exemple une fonction r cursive en la d finissant avec

son it r e.

28

} Il existe deux classes de syst mes LISP suivant la fa on

dont ce probl me est r solu :

a. Syst mes bi-valents

b. Syst mes mono-valents

29

a. Syst mes bi-valents :

Chaque symbole peut recevoir deux valeurs, une valeur comme

variable dite C-val et une valeur comme fonction dite F-val.

Exemple :

(setq a 3)

Nous mettons 3 dans la C-val de a

Les symboles +,-,*,... ont une F-val dans l'environnement initial.

Le symbole fib a une F-val partir de la d finition de la fonction

fib.

30

Pour avoir la d finition d'une fonction on utilise la fonction

pr d finie getdef

Exemple :

? (getdef 'fib)

Dans les syst mes bi-valents rien n'emp che de donner une valeur

la fois la C-val et la F-val d'un symbole.

Exemples de syst mes bivalents le-Lisp et Mac-Lisp.

31

b. Syst mes mono-valents :

Dans ces syst mes, un symbole ne peut recevoir qu'une

seule valeur dite C-val.

L' valuation de la fonction donne sa d finition

(pas besoin de getdef).

32

Nous avons vu que la valeur d'une liste est obtenue en

op rant le premier l ment, qui correspond au nom

de la fonction, sur les valeurs des autres l ments.

Mais prenons cet exemple :

? (setq a 5)

La r gle g n rale n'a pas t appliqu e : a n'a pas t

valu e puisqu'il s'agit de lui donner une valeur.

33

On distingue d'abord les primitives pr d finies et les fonctions

d finies par l'utilisateur :

SUBR: on appelle SUBR une fonction pr d finie crite en

langage machine valuant ses arguments.

EXPR ou LAMBDA: une fonction crite en LISP valuant ses

argument.

FSUBR: une fonction pr d finie crite en langage machine

n' valuant pas tous ses arguments (setq).

34

On peut obtenir le type d'une fonction gr ce la

primitive typefn.

Exemples :

?(typefn 'fact)

= expr

?(typefn 'car)

= subr1

?(typefn '*)

= nsubr

35

• Laddition

(+ & &)

• La soustraction

(- & &)

• La multiplication

(* & &)

• La division

(/ & &)

36

• QUOTE

• CAR

• CDR

• CONS

• APPEND

37

• Emp che l valuation de lexpression arithm tique

fournie en argument.

Retourne lexpression non valu e.

(quote <argument>)

Exemple :

? (quote (2 + 3))

= (2 + 3)

38

• Extrait le premier l ment dune liste. Celui-ci peut

tre un atome ou une liste.

(car <argument>)

Largument doit tre une liste.

39

• Retourne une liste priv e de son premier l ment.

(cdr <argument>)

Largument doit tre une liste.

40

• Les fonctions CAR et CDR peuvent tre imbriqu es,

cest- -dire appliqu es successivement sur une liste.

• (car (cdr <liste>)) -> (cadr <liste>)
• (car (cdr (cdr <liste>))) -> (caddr <liste>)
• (car (cdr (car (cdr <liste>)))) -> (cadadr <liste>)

41

Afin de lire correctement une imbrication

de fonctions, commencez par celle

inscrite en profondeur

42

Permet dextraire le troisi me l ment de la liste

fournie en argument.

(caddr (a b c)) = (car (cdr (cdr (a b c))))

= (car (cdr (b c)))

= (car (c))

= c

43

Ajoute un l ment en t te dune liste.

(cons <arg1> <arg2>)

Le nombre darguments est fixe = 2

44

Permet de concat ner les listes transmises en

arguments

(append <arg1> <arg2> & <argn>)

45

Constructeur et s lecteur de listes:

• Cons : permet d'ajouter un atome ou une liste en t te

d'une liste.

? (cons 2 '(3 4))

= (2 3 4)

? (cons '(1 2) '(3 4))

= ((1 2) 3 4)

46

Constructeur et s lecteur de listes :

(car <l>)

retourne la t te de la liste VALEUR<l>, retourne erreur si VALEUR<l>

n'est pas une liste.

(cdr <l>) retourne le reste de la liste VALEUR<l>, retourne erreur si

VALEUR<l> n'est pas une liste.

? (car '(1 2 3))

=1

? (car (cdr (cons 1 '(2 3))))

= 2

47

Constructeur et s lecteur de listes:

• (append <l1> ... <ln>)

retourne la liste obtenue en concat nant les listes <l1> ... <ln>

? (append '(ceci est ) '(un support de cours) '(en Lisp))

= (ceci est un support de cours en Lisp)

• (list <s1> ...<sn>)

retourne la liste dont les l ments <s1> ...<sn>.

? (list 1 2 '(3 4))

= (1 2 (3 4))

48

• (length <s>)

retourne le nombre d' l ments de plus haut niveau de <s>,

si <s> est une liste, sinon 0 (si <s> est un atome).

Exemple:

? (length '(a (b c) d))

= 3

49

Les fonctions pr dicats sont toujours valuantes,

elles retournent nil si le pr dicat est faux.

Si le pr dicat est vrai, la r ponse peut d pendre

des syst mes puisque "vrai" admet comme

repr sentation toute S-expression diff rente de

nil.

De nombreux syst mes utilisent l'atome "t".

50

• (atom <s>)

retourne "t" si VALEUR<s> est un atome num rique ou

symbolique, et retourne () si c'est une liste non vide.

• (null <s>)

retourne "t" si VALEUR<s> est gal () et () dans le cas

contraire.

• (eq <s1> <s2>)

permet de tester l'identit de deux atomes.

Si VALEUR<s1> et VALEUR<s2> sont identiques retourne

"t", sinon retourne ().

51

• (equal <s1> <s2>)

permet de tester si VALEUR<s1> est semblable VALEUR<s2>,

elle retourne t , sinon (). Elle admet comme arguments des

listes et des atomes.

• (symbolp <s>)

retourne "t" si <s> est un symbole, et retourne nil sinon.

• (constantp <s>)

retourne "t" si <s> est une constante, et retourne nil sinon.

Une constante est soit un nombre, une cha ne de caract res ou nil.

52

• (consp <s>)

retourne "t" si <s> est une liste non vide, et retourne nil

sinon.

• (listp <s>)

retourne "t" si <s> est une liste, et retourne nil sinon.

53

• (numberp <s>)

Teste si largument est un nombre. Retourne le nombre si le

test est v rifi , () sinon.

• = ou < ou > ou <= ou >=

Compare les arguments transmis par rapport aux crit res

dinf riorit ou de sup riorit . Retourne le 1er argument si le

crit re est v rifi , () dans le cas contraire.

• eqn =

54

Ce sont les fonctions pour lesquelles la valeur logique du

r sultat ne d pend que de la valeur logique des

arguments.

OR retourne une expression de valeur logique vraie si

l'un au moins des arguments est de valeur logique vraie

sinon retourne nil.

L valuation s'arr te d s le premier argument dont la

valeur est vraie. Pour cette raison OR est une F-SUBR.

55

• (or <s1> &<sN>)

retourne la valeur du premier argument dont la valeur est

diff rent de nil, et nil sinon.

L' valuation sarr te d s l'obtention dune valeur vraie.

• (and <s1> &<sN>)

retourne la valeur du dernier argument si les valuations de

tous les arguments sont vraies, et nil sinon.

L valuation sarr te d s lobtention dune valeur nil.

56

(progn <s1>

...

<sN>)

value s quentiellement ses arguments et

retourne la valeur du dernier.

Utile pour la structure conditionnelle IF.

57

-- la longueur au plus haut niveau

-- la longueur au plus bas niveau

(longueur1 l)

(longueur2 l)

(palindrome l)

(appartient e l)

(inverse l)

(intersection l1 l2)

(dernier l)

(lsd l)

-- la liste sans son dernier l ment

58

(nieme n l) -- l quivalent de nth en Lisp

(elem-rang-pair l)

(elem-rang-impair l)

(coupler l1 l2)

(extremites l)

(abs-list l)

(snoc l e) -- ajout dun l ment en queue dune liste

(subst new old l)

(aplatir l)

59

Op rateur LET

} En LISP, on tend privil gier une programmation

fonctionnelle et manipuler des fonctions au sens

math matique du terme.

Applications dun ensemble dans un autre pour lesquels

la notion daffectation nintervient pas.

Ceci nest pas incompatible avec la n cessit de sauvegarder

des r sultats interm diaires.

60

Op rateur LET

} La primitive LET offre le moyen de le faire.

} La fonction let est tr s utilis e pour proc der l' valuation

d'expressions dans un environnement provisoire.

} Elle permet de cr er des variables locales.

61

(let ((<var1> <s1>) ...(<varn> <sn>))

<expr1> ... <exprn>)

Cette fonction permet de :

• valuer successivement <s1>...<sn>
• lier <var1> ... <varn> aux valuations obtenues
• valuer successivement <expr1> ... <exprn>
• d lier <var1> ... <varn>
• retourner l' valuation de <exprn>

62

Exemple :

? (setq x 2 y 4)

= 4

? (let ((x (- x y)) (y (+ x y))) (* x y))

= -12

Les liaisons se font en parall le;

La deuxi me liaison, savoir, y (+ x y) se fait avec

la valeur de x ant rieure l'appel de let.

63

Dautres primitives de modification de la valeur dun symbole

permettent le parcours et la construction progressive de listes.

Elles facilitent la programmation de fonctions it ratives.

(nextl <v>) : retourne (car <v>) et affecte au symbole <v> la

valeur de (cdr <v>)

(newl <v> <e>) : affecte <v> la valeur de (cons <e> <v>) et

retourne cette valeur

(while <test> <e1>& <en>) : it re sur l valuation s quentielle de

<e1>& <en> tant que VALEUR<test> est diff rente de ().

64

Exemple : REVERSE it ratif

(de reverse (l)

(let ((resultat))

(while l (newl resultat (nextl l)))

resultat))

65

} La plupart des syst mes LISP poss dent dans le descriptif d'un

symbole un champ appel P-LIST permettant l'utilisateur

d'attacher aux symboles des propri t s.

} Le mode d'utilisation de ce champ varie d'un syst me un

autre. Le_Lisp attache la P-LIST d'un symbole une liste plate

de longueur paire appel e P-liste dont le format est le suivant :

(<prop1><val1> ... <propN><valN>)

Les indicateurs <prop1> ... <propN> indiquent une propri t et

sont suivis de la valeur de cette propri t .

66

La gestion de cette liste est assur e par les fonctions SUBR

suivantes :

• (plist <symb>) retourne la P-liste de symbole <symb>
• (plist <symb> <l>) affecte <l> la P-liste du symbole <symb>
• (putprop <symb> <val> <prop>) affecte <prop> la valeur

<val> dans la P-liste de symbole <symb>

• (getprop <symb> <prop>) retourne la valeur de <prop> dans la

P-liste <symb>

• (remprop <symb> <prop>) supprime, si elle existe, <prop> dans

la P-liste <symb>

67

La fonction EVAL value la valeur de son argument.

Exemple :

? (setq a '(* 2 4))

= (* 2 4)

? (setq x 'a)

= a

? x

= a

? (eval x)

=(* 2 4)

? (eval (eval x))

= 8

68

La fonction EVAL est appliqu e implicitement

par l' valuateur.

En l'appelant explicitement, on force une

deuxi me valuation.

69

• (print <expr>)

value son argument, dite la valeur obtenue et retourne

sa valeur.

Exemple:

? (setq a 3)

= 3

? (print a)

a

= 3

70

print est souvent utilis e avec des cha nes de caract res (entre ).

L'utilisation de print ne se justifie que lorsque le r sultat de

l' valuation n'est pas dit .

? (print 'salut)

salut

= salut

; on cr e le symbole salut

? (setq salut "Bonjour")

= Bonjour

? (print salut)

= Bonjour

71

• (read)

c'est une fonction 0-aire qui retourne sans l valuer la

r ponse de l'utilisateur (un ? est envoy par le syst me

pour l'inviter envoyer une expression).

Exemple :

? (setq x (read))

? 5 ; r ponse de l'utilisateur

= 5

72

• princh

Edite un certain nombre de fois le caract re transmis la

fonction.

(princh <caractere> <nombre>)

Exemple :

? (princh - 12)

= ------------

73

• terpri

Lappel sans arguments vide le tampon et commence une

nouvelle ligne (retourne nil).

(terpri <nombre>)

Dans le cas de la pr sence dun argument, celui-ci

correspond au nombre de sauts de lignes appliquer.

Exemple:

? (terpri 2)

= t ; apr s 2 sauts de ligne

74

Editeur pepe

Fonction dappel de pepe :

• (Ctrl E)
• (pepe <nom_fichier>)
• (pepe (pretty <nom_fichier>))

Charger un fichier :

• (load <nom_fichier>)

-^L<nom_fichier>

Effacer l cran :

• (tycls)

Quitter linterpr teur :

• (end)

75

La fonction Trace modifie la d finition d'une fonction :

la fonction dite une ligne chaque fois qu'elle est appel e

en indiquant les valeurs des variables.

On revient la d finition initiale par la fonction Untrace.

(trace <f>)

(untrace <f>)

La fonction Trace est tr s utile pour suivre les appels

d'une fonction r cursive.

76

La fonction Step permet une valuation pas pas.

(step <expr>)

Cette fonction donne avec plus de d tails au niveau

des op rations l mentaires, une valuation pas pas.

77

Avez-vous des QUESTIONS ?

?

78

Les op rations de s lection

La r cursivit

Fonctions r cursives sur les ensembles

Lit ration

79

Structure de la fonction IF

(if (condition)

(alors_action1)

(sinon_action2)

&

(sinon_action n))

; condition valuer

; action pour condition vrai

; actions pour condition fausse

80

(IF <s1> <s2> <s3>)

Si la valeur de <s1> est diff rente de NIL, IF retourne la valeur de

<s2>; sinon, IF value <s3>.

IF construit une structure de contr le de type "si alors sinon" .

Exemples :

? (IF T 1 2)

=1

? (IF NIL 1 2)

=2

? (IF NIL 1)

= NIL

81

(WHEN <test> <s1> ... <sN>)

Si <test> est Vrai, WHEN value chacune des expressions

<sI>.

(UNLESS <test> <s1> ... <sN>)

Si <test> est Faux, UNLESS value chacune des expressions

<sI>.

82

Structure de la fonction COND

(cond

((test1)

((test2)

&

(t

(action1))

(action2))

(actions par d faut)))

83

Exemple :

? (de test (x y)

(COND

((> x y)

((= x y)

(t

'sup)

'egal)

'inf)) )

= test

? (test 12 5)

= sup

?(test 5 8)

= inf

84

Concept fondamental :

En math matiques :

Une relation de r currence

En informatique :

Proc dures r cursives

85

En algorithmique :

f Fonction qui sappelle elle-m me

f Appels de plus en plus simples

f Solution directe pour le dernier appel

f Respect de la condition darr t

86

Correspondance entre les mod les :

Exemple : la factorielle

f D finition r currente :

n ! = n (n 1) !

pour n > = 1 avec 0 ! = 1

f Algorithme r cursif :

SI

ALORS

SINON

n = 0

r ponse = 1

r ponse = n * fact (n 1)

f Programme LISP :

(defun fact (n)

(cond

((= n 0)

(t

1)

(* n (fact (- n 1) ) ) ) ) )

87

3 * fact (2)

--------------

D roulement de la fonction pour Factorielle (3)

? (fact 3)

= 6

E

M

P

I

L

E

R

2 * fact (1) --------------

RETOUR DE LA PILE

D

E

P

I

L

E

R

--------------

1 * fact (0)

2 * 1 = 2

3 * 2 = 6

1 * 1 = 1

= 1

88

(ensemble l)

teste si une liste est un ensemble (pas de doublons)

(inclus l1 l2)

teste si tous les l ments dune liste se trouvent dans une autre

(compare l1 l2)

teste l galit de deux ensembles

(unique l)

transforme une liste en un ensemble (sans doublons)

(union l1 l2)

cr e un ensemble constitu des l ments de deux listes

(inter l1 l2)

cr e un ensemble constitu des l ments communs

89

Fonctions It ratives :

PROG&GO...RETURN

(prog <liste> <S-expr1> & <S-expr n>)

(go <atom>)

(return <S-expr>)

90

Exemple 1:

(defun puissance (n p)

(prog (resultat)

(setq resultat 1)

depart

(setq resultat (* n resultat))

(setq p (- p 1))

(if (= p 0)

(return resultat)

(go depart) ) ) )

91

Exemple 2: dernier l ment dune liste

(defun dernier (liste)

(prog ( )

encore

(cond

((null (cdr liste)) (return (car liste)))

(t (setq liste (cdr liste)))

)

(go encore)

)

)

92

Exemple 3: variante it rative de la factorielle

(defun factorielle (n)

(prog (resultat)

(setq resultat 1)

toujours

(cond

((= 0 n) (return resultat))

)

(setq resultat (* resultat n) n (- n 1))

(go toujours)

)

)

93

Fonctions It ratives :

WHILE

(WHILE (condition)

(S-expr 1)

(S-expr 2)

&

(S-expr n)

)

Elle value les S-expressions TANT QUE la condition retourne VRAI

94

Exemple 1: afficher le d compte dun nombre

(defun decompte (n)

(while (> n 0)

(print n)

(decr n)

)

)

; d cr mente n

95

Exemple 2: inverse version it rative (vu dans let)

(de reverse (l)

(let ((resultat))

(while l (newl resultat (nextl l)))

resultat))

96

Avez-vous des QUESTIONS ?

?

97

Les Fonctions Anonymes

Les Fonctionnelles de R cursion

Les Filtres

Les Macro Fonctions

98

(lambda <liste-arguments> <corps> )

(lambda (x) (+ x x))

(lambda (x y) (+ ( 2 x) ( 3 y)))

Une lambda-expression est appel e description

anonyme dune fonction.

99

(LAMBDA <param tres> <corps de la fonction> <valeurs locales>)

La fonction anonyme LAMBDA retourne l valuation

dune <fonction> avec des <param tres> qui prennent des

<valeurs locales>. En dehors de LAMBDA les param tres

sont d li s.

Elle permet de d finir une fonction sans nom qui n'est

pas utilisable hors de la S-expression dans laquelle elle est

d finie.

100

Exemples :

? ((lambda (x y) (* x y)) 2 3)

= 6

? (setq a '(lambda (x y) (* x y)))

= (lambda (x y)(* x y))

? (apply a '(2 3))

= 6

? ((lambda (x) (+ x x)) 3)

= 6

101

Fonction dordre sup rieur qui prend les

fonctions comme arguments et les applique sur

des ensembles de donn es.

102

} Ces fonctionnelles ont pour but d'appliquer une m me

fonction successivement diff rents morceaux d'une ou

plusieurs listes.

} APPLY

} MAPCAR

103

} (APPLY <f> <liste>)

retourne la valeur de l'application de la fonction < f > sur la

liste <liste>

Exemples :

? (apply '+ '(2 3 4) )

= 9

? (apply 'append '((a b) (c d)))

= (a b c d)

? (apply '/ ' (6 2))

? (apply 'modulo' (6 2))

= 3

= 0

104

} La fonctionnelle de r cursion la plus utilis e est mapcar.

} Cette fonctionnelle applique la fonction (suppos e

unaire) aux l ments successifs d'une liste (car, cadr,

caddr,...) et retourne la liste des r sultats de ces

applications.

} On peut utiliser aussi mapcar avec plusieurs listes.

105

Donc il existe deux utilisations de mapcar.

Usage1 :

(mapcar <s> <l>)

value <s> et applique le r sultat aux l ments de

la liste <l> et retourne la liste des r sultats.

Exemples :

? (mapcar '1+ '(1 2 3))

= (2 3 4)

? (mapcar 'car '((a b) (c) ((d e) f)))

=(a c (d e))

106

Usage 2 :

(mapcar <s> <l1> ... <ln>)

value <s> et applique le r sultat aux car des listes <l1> ... <ln>

puis

leurs l ments suivants (cadr, caddr,...) et retourne la liste des

r sultats.

Exemples :

? (mapcar '+ '(1 2 3) '(4 5 6))

= (5 7 9)

? (mapcar (lambda (x y) (+ ( x 2) ( y 3))) '(1 2 3) '(4 5 6))

= (14 19 24)

107

(let ((x a)) <expr>)

((lambda (x) <expr>) a)

Exemples :

(let ((x 2)) (+ x x)) ((lambda (x) (+ x x)) 2)

108

Soient les deux fonctions suivantes :

1. Retourner les plus petits quun l ment dans une liste

(de petits (a l)

(cond

((null l) ())

((< (car l) a) (cons (car l) (petits a (cdr l))))

(petits a (cdr l))))

(t

109

2. Retourner les plus grands quun l ment dans une liste

(de grands (a l)

(cond

((null l) ())

((>= (car l) a) (cons (car l) (grands a (cdr l))))

(grands a (cdr l))))

(t

110

Filtres

} Les deux fonctions petits et grands sont, lexception

des deux tests, rigoureusement identiques.

} Elles effectuent le m me travail : passer en revue les

l ments dune liste en les soumettant un test et ne

retenir que ceux qui passent le test.

} Alors peut-on programmer ceci en une fonction

g n rale qui prendrait comme argument la fonction de

test utiliser et la liste filtrer par ce test ?

111

Filtres

(de filtre (test l)

(cond

((null l) ())

((funcall test (car l)) (cons (car l)

(filtre test (cdr l)))

(t (filtre test (cdr l)))))

112

Filtres

} funcall

(funcall <fn> <s1> &<sn>) o <fn> d signe une fonction

qui sera appliqu e aux arguments <s1> &<sn>.

Exemple :

? (filtre (lambda (x) (>= x 9)) (15 7 12 3))

= (15 12)

113

Filtres

Nos deux fonctions petits et grands peuvent sexprimer

alors comme suit :

(de petits (a l)

(filtre (lambda (x) (< x a)) l))

(de grands (a l)

(filtre (lambda (x) (>= x a)) l))

Lint r t du filtre est de cr er une classe de fonctions tr s

g n rales pour s lectionner des l ments dans une liste.

114

} Les objets LISP sont trop complexes pour pouvoir tre

rang s dans un seul mot m moire.

} Ils sont en g n ral repr sent s par un pointeur.

} La cr ation des doublets de listes et des autres objets

Lisp se fait le plus souvent dynamiquement.

} Un dispositif g n ral appel GARBAGE-COLLECTOR

r cup re automatiquement les doublets et objets

inutilis s .

115

} Pointeurs et doublets

On appelle doublet (ou cons) un ensemble de deux pointeurs.

Nous le repr sentons par un diagramme en "bo tes et fl ches":

Une liste peut tre consid r e comme un ensemble ordonn de

deux l ments, le premier s'appelle le CAR et le second le

CDR de la liste. On repr sente donc une liste par un doublet

dont la premi re partie pointe vers le CAR et la seconde vers le

CDR de la liste.

116

} Pointeurs et doublets

Exemples :

a. Repr sentation en m moire de la liste

(LISP LANGAGE FONCTIONNEL).

117

} Pointeurs et doublets

b. Repr sentation de la liste (A (B A) B) par un diagramme en

bo tes et fl ches.

118

119

120

121

122

123

(ajoutN e n l)

Ecrire une fonction ajoutN qui ajoute un l ment la ni me position dune

liste.

(rech e p l)

Ecrire une fonction rech qui cherche si un l ment e se trouve la position p

dune liste l.

(pair l)

retourne la liste des l ments pairs dune liste (Utiliser les Filtres)

(impair l)

retourne la liste des l ments impairs dune liste (Utiliser les Filtres)

(list-abs-mapcar l)

Ecrire une fonction qui retourne la liste des valeurs absolues des l ments

dune liste (Utiliser mapcar)

Ecrire une fonction qui retourne f(1). Appliquer cette fonction f(x) = 3x + 2

124

Ecrire une variante de la fonction mapcar :

mapcar-fill (f l1 l2)

o f est une fonction, l1 et l2 des listes et qui retournent la m me

chose que mapcar si les deux listes sont de m me longueur et une

liste dont les premiers l ments sont les m mes que ce qui est

renvoy par mapcar et le reste des l ments sont les l ments

suppl mentaires de la liste la plus longue.

Exemples :

? (mapcar-fill + (1 5 8) (3 4 2))

= (4 9 10)

? (mapcar-fill + (1 5 8) (3 4 2 6 7 4 2))

= (4 9 10 6 7 4 2)

125

Ecrire une fonction mappend (fun l) qui applique la

fonction fun chaque l ment de la liste l (et dont le r sultat

doit tre une autre liste) puis renvoie la concat nation des

r sultats ainsi obtenus.

Exemple :

? (mappend (lambda (x) (list x (1+ x))) (5 3 9 2 5))

=(5 6 3 4 9 10 2 3 5 6)

? (mapcar (lambda (x) (list x (1+ x))) (5 3 9 2 5))

= ((5 6) (3 4) (9 10) (2 3) (5 6))

126

Ecrire une fonction combien qui retourne le nombre d l ments de la liste

v rifiant un pr dicat.

Exemples :

(combien 'evenp '(1 5 7 6 2))

= 2

(combien 'numberp '(2 3 4 a b 5 t + 8))

= 5

(combien (lambda (x) (= (modulo x 2) 0)) '(1 5 7 6 2))

= 2

Ecrire une fonction TRI qui affiche un menu permettant lutilisateur de choisir

un algorithme de tri appliquer. La liste trier est saisie au clavier.

127

(de next-line (l) (mapcar + (cons 0 l) (append l (list 0))))

1. Tester la fonction next-line en lappliquant n fois la liste (1).

2. En utilisant la fonction next-line, crire une fonction triangle (n) qui construit une

liste contenant les listes correspondant aux lignes du triangle de Pascal dordre n.

Exemples :

(triangle 0)

((1))

(triangle 1)

((1) (1 1))

(triangle 2)

((1) (1 1) (1 2 1))

(triangle 3)

((1) (1 1) (1 2 1) (1 3 3 1))

(triangle 4)

((1) (1 1) (1 2 1) (1 3 3 1) (1 4 6 4 1))

128