scheme - Comment expliquer une sortie comme celle-ci?

Question

J'ai donné les définitions suivantes:

(define head car) 

(define (tail stream) (force (cdr stream))) 

(define (addL x y)(cons-stream (+ (head x) (head y))(addL (tail x) (tail y)))) 

(define fibs(cons-stream 1(cons-stream 1 
    (addL (tail fibs) fibs)))) 

(define (reorder order-stream data-stream) 
    (cond ((stream-null? order-stream) the-empty-stream) 
     ((stream-null? data-stream) the-empty-stream) 
     (else (cons-stream (stream-ref data-stream (stream-first order-stream)) 
       (reorder (stream-rest order-stream) data-stream))))) 

Et on m'a demandé d'afficher les 7 premiers chiffres (que je vais montrer ci-dessous) et d'expliquer ces chiffres qui sont émis par cette ligne de code:

(reorder (tail fibs) (tail fibs)) 

la sortie des 7 premiers éléments du flux résultant est:

"2, 3, 5, 13, 55, 610, 28657"

Quelqu'un at-il une idée pour une explication de cela? Je ne comprends pas tout à fait ce qui se passe réellement ici ...

Answer 1

Eh bien, fibs est le flux infini (paresseux) des nombres de Fibonacci,

fibs = 1 , ft ... 
ft = 1 , (addL fibs ft) ... 
; 1, 1, 2, 3, 5, 8, 13, .... 

Permettez-moi d'écrire la définition reorder dans un pseudocode, il est donc plus facile à suivre, en tant

(reorder js xs) = empty       | if (empty? js) or (empty? xs) 
       = xs[js[0]] , 
        (reorder (rest js) xs) ... | otherwise 

Notez que xs est transmise sans changement, et js est repris son élément de tête de chaque itération. Cela signifie que (reorder (stream i j k ... n ...) xs) prend progressivement la i e, puis j th, k th ... n e, ... des éléments du flux xs.

Depuis l'appel est (reorder ft ft), la séquence produite est

ft[ft[0]], ft[ft[1]], ft[ft[2]], ... 

à savoir

ft[1], ft[2], ft[3], ft[5], ft[8], ft[13], .... 

qui est ce que vous voyez.