Recursive streams (Haskell)

หลายคนคงเคยเห็นตัวอย่าง function ที่ทำหน้าที่หาค่า Fibonacci แบบ recursive ธรรมดามาแล้ว

fib 0 = 1
fib 1 = 1
fib n = fib(n-1) + fib(n-2)

ใน haskell มันมีเทคนิคตัวหนึ่งที่เรียกว่า recursvie stream
ซึ่งเราสามารถนำมา apply หาค่า Fibonacci ได้

fibs = 1:1:zipWith (+) fibs (tail fibs)

หลักการก็คือ ถ้าเราสังเกตุค่า Fib ดู

1 1 2 3 5 8  13 21 ...  ค่า fib sequence
1 2 3 5 8 13 21 34 ...  tail fib (function tail จะทำการตัดตัวหน้าสุดทิ้ง)

ทั้งสองบรรทัดข้างบนบวกกันได้
2 3 5 8 13 21 34 55
ซึ่งก็คือ tail of tail of fib sequence

เมื่อนำหลักการข้างบนมาเขียน function fibs
fibs ก็เลยเท่ากับ 1 ตาม ด้วย 1 และตามด้วย ค่า fib บวกด้วย tail ของ fib

แต่ Diagram ที่ช่วยให้ผมเห็นภาพได้ดียิ่งขึ้น ก็คือ diagram นี้



เป็น diagram ที่อยู่ในหนังสือ The Haskell School of Expression
ของ Paul Hudak