Accueil
Professeur et Démonstrateurs
Horaires et locaux
Notes de cours
Démonstrations et devoirs
Examens
Liens utiles
Au sujet du livre de cours
Consultez vos notes
Foire aux questions (FAQ)
|
|
Démonstration 7: S'en sortir honnêtement avec Scheme
Note: Le "baratin" de la semaine est un sous-ensemble des notes de démonstrations du cours de Yoshua Bengio (http://www.iro.umontreal.ca/~bengioy/ift2030/A01/Demo1-scheme.htm)
Structures de données
Scheme utilise essentiellement les listes, mais d'autres structures de
données sont aussi proposées.
a) Les listes et les paires
-
Une liste est un ensemble d'élement de types pas nécessairement
homogènes entourés par des parenthèses et séparés
par un espace. C'est une strcuture de données qui est modifiable.
Toute expression qui n'est pas une constante ou une variable est nécessairement
une liste.
On peut construire une liste avec la procédure list, la procédure
cons ou le quote:
>(define a (cons 1 '()))
>a
(1)
>(car a)
1
>(cdr a)
()
>(list? a) ; prédicat
pour savoir si a est une liste
#t
La liste vide est représentée par `() et
n'est pas une paire
-
Exemples de listes:
(3 x 5)
(+ 3 4)
-
Exemple de construction avec la procédure list
ou le quote:
>(define x 1)
>(define b (list 1 2 x))
; ici x est évalué
>(define c '(1 2 x))
; ici x est un symbole
>b
(1 2 1)
>c
(1 2 x)
>(car c) ; retourne le premier élément
de la liste
1
>(cdr c) ; retourne une liste
(2 x)
>(cadr c) ; équivalent
à (car (cdr c))
2
>(cddr c) ; équivalent
à (cdr (cdr c))
(x)
>(caddr c) ; équivalent
à (car (cdr (cdr c)))
x
>(cdddr c) ; équivalent
à (cdr (cdr (cdr c)))
()
>(define d '((1 2) 3 4))
>(car d)
(1 2)
>(caar d) ; équivalent
à (car (car d))
1
-
Pour utiliser une liste en tant que liste et non en tant qu'application
préfixe d'une procédure ou forme spéciale, on utilise
le quote, ou la procédure list:
> (define
l '(1 2 a))
>l
(1 2 a)
>(define l (list 1 2 'a))
Remarque
Le nombre de compostion de car et/ou cdr
est limité à 4.
-
Une paire contient deux champs, on les nommes car et
cdr. On construit une paire avec la procédure cons
:
>(define a (cons 1 2))
>a
(1 . 2)
>(car a) ;
retourne le champ car
1
>(cdr a) ;
retourne le champ cdr
2
>(pair? a) ; prédicat
pour savoir si a est une paire
#t
Quelques opérations sur les listes:
-
Opérations append, length, reverse, list-ref
>(define d '((1 2) 3 4))
>(length d) ; Nombre d'éléments
dans la liste
3
>(append d '(5 (6 7) 8))
; Concaténation
((1 2) 3 4 5 (6 7) 8)
>(reverse d) ; Renverse les éléments
(4 3 (1 2))
>(list-ref d 2) ; Retourne le 3-ieme élément de la liste.
4
>(list-ref d 0) ; Retourne le premier élément de la liste.
(1 2)
-
Transformations list->string, string->list
>(string->list "Hello"); Conversion chaîne de caractàres - liste
(#\H #\e #\l #\l #\o)
>(list->string '(#\H #\e #\l #\l #\o)); Conversion liste - chaîne de caractàres
"Hello"
-
Recherche dans les listes:
La recherche dans les listes peut être effectuée
à l'aide des fonctions "member". Ces fonctions retournent
la sous-liste commençant par l'élément trouvé,
et #f si l'élément n'a pu être trouvé.
>(memq c '(a b c d e)) ;
utilise eq? pour trouver l'élément
(c d e)
>(memv 3 '(1 2 3 4 5))
; utilise eqv? pour trouver l'élément
(3 4 5)
>(member '(3 4) '((1 2) (3 4) (5 6)))
; utilise equal? pour trouver l'élément
((3 4) (5 6))
>(member 7 '(1 2 3 4 5))
#f
Les expressions (suite)
b) Let, Let* et Letrec
Les commandes let, let* et letrec* permet la formation des blocs d'expressions
en scheme. Ils sont syntaxiquement identique mais la portée des
variables liées est différentes dans chacun des cas.
-
Dans le cas de let (let <bindings> <body>) les valeur initiales sont
évaluées avant de lier les variables contenus dans la section
de liens <bindings> Dans l'exemple suivant bien que x soit lié
à la valeur 2 dans la section de liage, l'évaluation de y
prendra la valeur initial de x qui est de 4 (define x 4) et donc le résultat
sera 6 et non pas 4.
>(define x 4)
(let ((x 2) (y x)) (+ x y))
-
Dans le cas de let* le liage et l'évaluation se font séquentiellement
de ce afit si on remplace l'instruction précédente let par
let* on obtient :
>(define x 2)
>(let* ((x 0) (y x)) y)
0
La forme let* (let*
<bindings> <body>) permet d'utiliser les variables précédemment
définies dans la liste.
-
Dans le cas de letrec les liaisons sont déjà effective lorsque
les valeurs initiales sont évaluées, ce qui permet une définition
mutuellement reccursive comme dans l'exemple suivant :
>(letrec ((even?
(lambda (n)
(if (zero? n)
#t
(odd?
(- n 1)))))
(odd?
(lambda (n)
(if (zero?
n)
#f
(even? (- n 1))))))
(even? 88))
>#t
c) Lambda expression
Le lambda-calcul est fondamental en Scheme. Brièvement, on
peut dire qu'il s'agit de fonctions anonymes, c'est à dire des objets
qui s'évaluent à
une fonction, sans nécessairement être liés à
une quelconque variable.
(lambda a b) ; définition d'une fonction.
Arguments dans a et corps dans b.
Exemples concrets:
>(define succ (lambda (x) (+ x 1)))
>(succ 2)
3
Je viens donc de définir une fonction qui
retourne le successeur de son argument et j'ai assigné cette fonction
à la variable succ, pour ensuite
pouvoir appeller succ normalement. Il existe un moyen pour enlever
cette assignation, c'est d'utiliser directement la définition de
la fonction pour
l'appliquer:
>((lambda (x) (+ x 1)) 2)
3
Ici j'ai tout simplement remplacé succ par
sa définition. Un autre exemple:
>(define (make-adder x) (lambda (y) (+ x y)))
>(define add1 (make-adder 1))
>(define add5 (make-adder 5))
>(add1 2)
3
>(add5 2)
7
La fonction make-adder prend l'argument x et produit une fonction qui
retourne son argument augmenté de x. C'est ce qui explique
que add1 soit
une fonction qui retourne le successeur de son argument.
d) map et apply
En Scheme, il peut être intéressant d'appliquer une procédure
à tous les éléments d'une liste pour ensuite obtenir
une liste contenant les résultats de ces applications. On
peut utiliser pour ce faire la fonction map, qui prend 2 arguments:
(map <func> <list>). Map construit alors une liste contenant
les résultats de l'application de <func> sur les éléments
de la liste <list>. Quelques exemples:
>(map (lambda (x) (+ x
1)) '(1 2 3 4 5))
(2 3 4 5 6)
>(map car '((a b) (c d) (e f)))
(a c e)
De manière plus générale, on
peut utiliser map sur plusieurs listes:
>(map + '(1 2 3 4 5) '(2 3 4 5 6))
(3 5 7 9 11)
Il est à noter que les listes doivent alors
avoir le même nombre d'éléments.
Pour appliquer une procédure à une liste de paramètres,
on peut utiliser la procédure apply. La forme d'un appel à
apply est la suivante:
(apply <func> <arg1> ... <argn> <argf>).
D'abord, apply évalue la fonction <func> et chacun des ses
arguments <arg1> ... <argn> et <argf>. Elle appelle ensuite
la fonction évaluée avec <arg1> ...<argn> comme n premiers
paramètres et <argf> comme la liste contenant le reste des paramètres.
-
La première forme prend d'abord <func>, la procédure à
appliquer, suivi d'une liste <args> d'arguments à passer en paramètre
à <func>.
-
La deuxième forme est équivalente à: (apply
<func> (append (list <arg1> ... <argn>) <argf>)
Donc on passe les n premiers arguments suivis du reste des arguments dans
la liste <argf>. Les cas où n=0 ou argf='() sont aussi
possibles:
Ici on appelle <func> avec la liste d'arguments <argf>.
(apply <func> <arg1> ... <argn> '())
Ici on appelle <func> avec la liste d'arguments (<arg1>
... <argn>). Cette dernière forme correspond à la forme
mieux connue:
(<func> <arg1> ... <argn>)
Exemples:
>(define (poly-degre-2 a b c) (lambda (x)
(+ (* a x x) (* b x) c))) ; Ici poly-degre-2 est une fonction
qui génère des polynômes du second degré
>((poly-degre-2 1 2 3) 2)
11
>((apply poly-degre-2 '(1 2 3)) 2)
11
>((apply poly-degre-2 1 (list 2 3)) 2)
11
>((apply poly-degre-2 1 2 '(3)) 2)
11
>((apply poly-degre-2 1 2 3 '()) 2)
11
Recursivité dans Scheme
-
La récursivité en Scheme est très utile. Les
interprètes Scheme implémentent l'optimisation de récursivité
terminale, ce qui permet d'obtenir des formes récursives aussi rapides
que des formes itératives équivalentes. Tout d'abord,
un exemple simple, la fonction length qui calcule le nombre d'éléments
d'une liste donnée. Je pourrais définir cette fonction de
la façon suivante:
>(define length (lambda (liste)
(if (null? liste)
0
(+ 1 (length (cdr liste)))))
Travail pratique (pas noté mais fortement recommandé)
Manipulations des listes
A) Écrire une fonction Scheme qui additionne les éléments d'une liste:
B) Écrire la fonction Scheme "aucun-zero" qui retourne un Booléen indiquant si une liste de nombres contient aucun zéro:
C) Écrire la fonction Scheme "même-longueur" qui retourne un Booléen indiquant si deux listes ont la même longueur:
> (meme-longueur '(3 4 5) '(a b c))
> (meme-longueur '(3 4 5) '(a b c d e f))
D) Écrire la fonction Scheme "minimum" qui retourne le plus petit élément d'une listes de nombre. La liste contient au moins un nombre:
E) Écrire la fonction Scheme "decompte" qui, étant donné un entier "n", retourne la liste des entiers de n-1 à 0:
F) Écrire la fonction Scheme "compte" qui, étant donné un entier "n", retourne la liste des entiers de 0 à n-1:
|
[top] |