Hiểu được thực hiện một thi fibonacci lười biếng trong Clojure

Question

Tôi đang cố gắng để hiểu việc thực hiện các đoạn mã sau:

(def fibs 
    (concat (lazy-seq [0 1]) (lazy-seq (map + fibs (rest fibs))))) 

Đây là những gì tôi mong chờ việc thực hiện để trông giống như

[0 1 : (map + [0 1] [1]) => 1 
[0 1 1 : (map + [0 1 1] [1 1]) => 1 2 
[0 1 1 1 2 : (map + [0 1 1 2] [1 1 2]) => 1 2 3 
[0 1 1 1 2 1 2 3 : (map + [0 1 1 2 3] [1 1 2 3]) => 1 2 3 5 
[0 1 1 1 2 1 2 3 1 2 3 5 .... 

Rõ ràng là không chính xác, vì kết quả là sai. Việc thực hiện duy nhất tôi có thể đưa ra rằng sản xuất kết quả chính xác là:

[0 1 : (map + [0 1] [1]) => 1 
[0 1 1 : (map + [1 1] [1]) => 2 
[0 1 1 2 : (map + [1 2] [2]) => 3 
[0 1 1 2 3 : (map + [2 3] [3]) => 5 
[0 1 1 2 3 5 .... 

Đây có phải là "đại diện" chính xác của tình trạng đầu và đuôi trong khi thực hiện? Nếu vậy, tại sao (rest fibs) trả về một mục duy nhất? Có phải vì một cuộc gọi đệ quy như (nghỉ ngơi (nghỉ ngơi (nghỉ ngơi [1 1 2 3])))?

Answer 1

Sợi là (0 1 ...) (vì số (concat [0 1] ...) ngay từ đầu). (rest fibs) là (1 ...). Sau đó (map + fibs (rest fibs)) là

((+ 0 1) ...) => (1 ...) 

Vì vậy fibs là (0 1 1 ...). Kể từ khi chúng tôi đã nhận mục kế tiếp, chúng ta có thể tính toán được nêu ra nhau:

(1 (+ 1 1) ...) => (1 2 ...) 

Và nó đi vào ...

(1 2 (+ 1 2) ...) 

Hãy suy nghĩ về fibs như thể nó đã có được, và tiểu bang của (map + fibs (rest fibs) khi di chuyển trên danh sách các fibs đã tồn tại (đó là tốt bởi vì nó kết thúc lên tính toán tất cả mọi thứ chúng ta cần trên đường).

Nó cũng có thể giúp đỡ để chỉ cần viết xuống hai chuỗi:

(0 1 1 2 3 5 ...) 
+(1 1 2 3 5 ...) 
=(1 2 3 5 8 ...) 

(Tôi muốn vẽ mũi tên ở đây để chỉ ra những gì chúng ta đã có và hiển thị kết quả đi, nhưng tôi không thể làm điều đó ở đây thật tốt).