Informatique et recherche
opérationnelle
IFT2030

Concepts des langages de programmation

Automne 2002


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]


Dernière mise à jour : Tue Nov 19 17:17:32 EST 2002
dift2030@iro.umontreal.ca