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 8: À l'aise avec Scheme
Note: Pas de "baratin" cette semaine, vous démonstrateurs aborderons avec vous la récursivité profonde avec comme exemple l'implémentation de la méthode equal . Pour le reste, un seul conseil: pratiquez Scheme en faisant les exercices qui vous sont proposés.
Travail pratique (pas noté mais fortement recommandé)
Révisions sur les listes
- A) Sans vous aidez de votre interpréteur Scheme, évaluez les expressions suivantes (vérifiez votre réponse avec l'interpréteur):
(cdr '((a (b c) d)))
(car '((a (b c) d)))
(car (cdr (cdr '(a (b c) (d e)))))
(car (cdr '((1 2) (3 4) (5 6))))
(cdr (car '((1 2) (3 4) (5 6))))
(car (cdr (car '((cat dog hen)))))
(cadr '(a b c d))
(cadar '((a b) (c d) (e f)))
- B) Pour chacune des listes qui suivent indiquez comment extraire
le symbole
a à l'aide des méthodes car et
cdr :
(b c a d)
((b a) (c d))
(((a)))
- C) Écrire la fonction
Second qui retourne le
deuxième élément d'une liste
- D) Écrire la fonction
Third qui retourne le
troisième élément d'une liste
- E) Soit la méthode:
(define mystere
(lambda (list-1 list-2)
(cons (car list-1) (cons (car list-2) '()))))
Indiquez la valeur des expressions suivantes (vérifiez votre réponse à
l'aide de l'interpréteur):
(mystere '(1 3 5 7) '(2 4 6))
(mystere '((a b) (c d)) '((e f) (g h)))
- F) Écrire la fonction
last-item qui retourne le
dernier élément d'une liste
- G) Écrire la fonction
ref-liste qui retourne l'élement d'indice n d'une liste:
(ref-liste 0 '(1 2 3 4)) -> 1
(ref-liste 2 '(1 2 3 4)) -> 3
- H) Écrire la fonction
remove-first qui prend en
argument un élément e et une liste l et qui
retourne une liste où la première occurrence de e est
éliminée:
(remove-first '1 '(2 1 1 2 3)) -> (2 1 2 3)
(remove-first '3 '(2 3 1 1 2 3)) -> (2 1 1 2 3)
- I) Que vaut l'appel suivant ?
(define mystery
(lambda (ls)
(if (null? (cddr ls))
(cons (car ls) '())
(cons (car ls) (mystery (cdr ls))))))
(mystery '(1 2 3 4 5))
- J) Écrire la fonction
list-first qui prend en
argument une liste dont chaque élément est une sous-liste et qui retourne une liste de chaque premier élément de chaquer sous-liste de niveau 1:
(list-of-first-items '((a) (b c d) (e f))) -> (a b e)
(list-of-first-items '((1 2 3) (4 5 6))) -> (1 4)
(list-of-first-items '((one))) -> (one)
|
Révisions sur les fonctions
- A) Écrire une méthode qui calcule la somme harmonique des n
premiers entiers (n est ici le paramètre). On rappelle que la somme
harmonique des n premiers entiers est la série: 1 + 1/2 + 1/3 + .. + 1/n
- B) Écrire une méthode
n-first qui retourne une liste des n premiers éléments de la liste passée en argument:
(n-first '(1 2 3 4 5) 2) -> (1 2)
(n-first '(1 2 (3 4) 5) 3) -> (1 2 (3 4))
- C) Écrire une méthode
sum qui calcule la somme des éléments d'une liste passée en argument:
(sum '(1 2 3)) -> 6
-
- D) Écrire une méthode
prod qui calcule le produit
des éléments d'une liste passée en argument:
(prod '(4 2 3)) -> 24
- D) Écrire une méthode
pair-sum qui calcule la somme élément à élément de deux listes de même longueur:
(pair-sum '(1 2 3) '(3 2 1)) -> (4 4 4)
(pair-sum '(1 2 3) '(2 3 4)) -> (3 5 7)
- E) Écrire une méthode
wrapa qui entoure un élément passé en argument de n niveaux de parenthèse, où n est également passé en argument:
(wrapa 'ift2030 2) -> ((ift2030))
(wrapa 'ift2030 4) -> ((((ift2030))))
- F) Écrire une méthode
list->int qui retourne
l'entier dont les chiffres sont ceux de la liste passée en argument:
(list->int '(1 2 3)) -> 123
(list->int '(1 3 2 3)) -> 1323
|
Des fonctions plus sérieuses
- A) Écrire un méthode
merge qui prend en paramètre deux
listes triées et qyui retourne une liste triée contenant les éléments
des deux listes:
(merge '(1 3 5 6) '(2 2 4 5 7))) -> (1 2 2 3 4 5 5 6 7)
- B) Écrire un méthode
deep-1 qui prend en paramètre une
liste et qui retourne une liste dans laquelle tous les élémentds de
premiers niveaux ont été parenthésés:
(deep-1 '(1 3 5 6)) -> ((1) (2) (3) (5) (6))
(deep-1 '((1 3) (5) 6)) -> (((1 3)) ((5)) (6))
- C) Écrire un méthode
subst-all qui prend en
paramètre deux éléments to et from et une
liste l et qui retourne une nouvelle liste où toute
occurrence defrom a été remplacée par to
dans l :
(subst-all 'z 'a '(a (b (a c)) (a (d a)))) -> (z (b (z c)) (z (d z)))
(subst-all 0 '(1) '(((1) (0)))) -> ((0 (0)))
- D) Écrire une méthode
prof qui retourne la profondeur
d'une liste:
(prof '((1 3) (5 7) (9 11))) -> 2
(prof '(1 (3 (5 (7 (9)))))) -> 5
(prof '(1 2)) -> 1
(prof '()) -> 0
- E) Écrire une méthode
flat qui applatit une liste:
(flatten '((1 3) (5 7) (9 11))) -> (1 3 5 7 9 11)
(flatten '(1 (3 (5 (7 (9)))))) -> (1 3 5 7 9)
(flatten '()) -> ()
(flatten '(1 2 3)) -> (1 2 3)
- F) Écrire une méthode
member-all? qui retourne #t si
l'élément passé en paramètre est membre (à un niveau quelconque) de la
liste passée en argument, et #f sinon:
(member-all? '1 '(2 (3 (1 3 1)))) -> #t
(member-all? '1 '(2 (3 (2 3 (1))))) -> #t
(member-all? '5 '(2 (3 (2 3 1)))) -> #f
- G) Écrire une méthode
remove-left-most qui prend en
argument un élément e et une liste et qui retourne une
liste où la première occurrence (quelque soit son niveau) de
e est supprimée:
(remove-left-most 'b '(a (b c) (c (b a)))) -> (a (c) (c (b a)))
(remove-left-most '(c d) '((a (b c)) ((c d) e))) -> ((a (b c)) (e))
- H) Écrire une méthode
left-most qui retourne l'atome (entier, symbole, chaine, ect.) le plus à gauche dans une liste:
(left-most '((((( 5 1))) 2) (2 ((2))) ((3)) (4 (2 5))) ) -> 5
(left-most '(2 (((3))) ((2 (3))))) -> 2
- I) Écrire une méthode
right-most qui retourne l'atome (entier, symbole, chaine, ect.) le plus à droite dans une liste:
(left-most '((((( 5 1))) 2) (2 ((2))) ((3)) (4 (2 5))) ) -> 5
(left-most '(2 (((3))) ((2 (3))))) -> 3
- J) Écrire une méthode
uniq qui retourne une liste privée de ses doublons successifs:
(uniq '(1 2 3 3 3 4 5 5 6 7 8 8 9 10)) -> (1 2 3 4 5 6 7 8 9 10)
(uniq '(1 2 3 3 1)) -> (1 2 3 1)
|
Des fonctions encore plus sérieuses
- A) Évaluez les expressions suivantes (vérifiez avec votre interpréteur):
(let ((a 5))
(let ((fun (lambda(x) (max x a))))
(let ((a 10) (x 20))
(fun 1))))
(let ((a 1) (b 2))
(let ((b 3) (c (+ a b)))
(let ((b 5))
(cons a (cons b (cons c '()))))))
- B) Évaluez les expressions suivants (vérifiez avec votre interpréteur):
(letrec
((loop
(lambda (n k)
(cond
( (zero? k) n )
( (< n k) (loop k n) )
( else (loop k (remainder n k)))))))
(loop 9 12))
(letrec
((loop
(lambda (n)
(if (zero? n)
0
(+ (remainder n 10) (loop (quotient n 10)))))))
(loop 1234))
- C) Que fait ce code?
(letrec ((mystery
(lambda (tuple odds evens)
(if (null? tuple)
(append odds evens)
(let ((next (car tuple)))
(if (odd? next)
(mystery (cdr tuple)
(cons next odds)
evens)
(mystery (cdr tuple)
odds
(cons next evens))))))))
(mystery '(1 2 3 4 5 6 7 8 9 10) '() '()))
- D) Que fait ce code?
(define mystery
(lambda (n)
(letrec ((mystery-helper
(lambda (n s)
(cond
( (zero? n) (list s) )
( else
(append
(mystery-helper (- n 1) (cons 0 s))
(mystery-helper (- n 1) (cons 1 s))))))))
(mystery-helper n '()))))
|
[top] |