5 Flots
Au fil des flots ou comment manipuler des listes infinies.
On rappelle que les flots sont manipulés comme suit:
;;;
(define-macro (cons-stream head tail)
`(cons ,head (delay ,tail)) )
(define (head stream)
(car stream) )
(define (tail stream)
(force (cdr stream)) )
(define (make-empty-stream)
'() )
(define (empty-stream? stream)
(null? stream) )
Exercice 44 : Définir la fonction map-stream1 qui applique une fonction sur
tous les termes d'un flot.
Solution de l'exercice 44 :
;;;;;;;;;;;;;;;;
;;;
(define (map-stream1 fonction stream)
(if (empty-stream? stream)
the-empty-stream
(cons-stream (fonction (head stream))
(map-stream1 fonction (tail stream)) ) ) )
Exercice 45 : Définir le flot des entiers naturels. On pourra pour cela utiliser
la fonction précédente (map-stream) et le flot des entiers
naturels lui-même.
Solution de l'exercice 45 :
(define integers
(cons-stream 0 (map-stream (lambda (n) (+ 1 n)) integers)) )
Exercice 46 : Concevoir une fonction retournant les n premiers termes d'un flot.
Par exemple:
? (EXTRAIRE INTEGERS 10)
= (0 1 2 3 4 5 6 7 8 9)
Solution de l'exercice 46 :
(define (extraire stream n)
(if (empty-stream? stream)
the-empty-stream?
(if (> n 0)
(cons (head stream)
(extraire (tail stream) (- n 1)) )
'() ) ) )
Exercice 47 : Écrire la fonction fusionnant équitablement deux flots. Par
exemple:
? (EXTRAIRE
(FUSIONNER INTEGERS (MAP-STREAM - INTEGERS))
10)
= (0 0 1 -1 2 -2 3 -3 4 -4)
Solution de l'exercice 47 :
(define (fusionner stream1 stream2)
(if (empty-stream? stream1)
stream2
(if (empty-stream? stream2)
stream1
(cons-stream (head stream1)
(cons-stream (head stream2)
(fusionner (tail stream1)
(tail stream2) ) ) ) ) ) )
Exercice 48 : Étendre la fonction map-stream afin qu'elle puisse traiter
un, deux ou plusieurs flots. La fonction s'arrêtera dès qu'un des
flots se tarit.
Solution de l'exercice 48 :
(define (map-stream fonction . streams)
(case (length streams)
((0) the-empty-stream)
((1) (map-stream1 fonction (car streams)))
(else
(if (any? empty-stream? streams)
the-empty-stream
(cons-stream (apply fonction (map head streams))
(apply map-stream fonction (map tail streams)) ) ) ) ) )
Exercice 49 : Quels sont les premiers termes de la suite qui fusionnée avec les
entiers naturels est identique à elle-même.
Solution de l'exercice 49 :
(define self-integers
(cons-stream (head integers)
(fusionner self-integers (tail integers)) ) )
Les premiers termes sont:
? (EXTRAIRE SELF-INTEGERS 25)
= (0 0 1 0 2 1 3 0 4 2 5 1 6 3 7 0 8 4 9 2 10 5 11 1 12)
? (EXTRAIRE (FUSIONNER INTEGERS SELF-INTEGERS) 25)
= (0 0 1 0 2 1 3 0 4 2 5 1 6 3 7 0 8 4 9 2 10 5 11 1 12)
Notez que l'on ne peut écrire directement l'expression auto-référente
(define self-integers (cons-stream integers self-integers)).
Exercice 50 : Le problème dit de Hamming est d'obtenir la liste des entiers
multiples de 2, 3 ou 5 en ordre croissant. Le résoudre.
Solution de l'exercice 50 :
(define hamming
(let ((integers+ (tail integers)))
(ordonner <
(map-stream (lambda (n) (* 2 n)) integers+)
(ordonner <
(map-stream (lambda (n) (* 3 n)) integers+)
(map-stream (lambda (n) (* 5 n)) integers+) ) ) ) )
(define (ordonner predicat stream1 stream2)
;;
(if (empty-stream? stream1)
stream2
(if (empty-stream? stream2)
stream1
(cond ((predicat (head stream1) (head stream2))
(cons-stream (head stream1)
(ordonner predicat (tail stream1) stream2) ) )
((predicat (head stream2) (head stream1))
(cons-stream (head stream2)
(ordonner predicat stream1 (tail stream2)) ) )
(else (ordonner predicat stream1 (tail stream2))) ) ) ) )
Le début de ce flot est
? (EXTRAIRE HAMMING 25)
= (2 3 4 5 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32 33 34)