fibs@(_ : tfibs) = 0 : 1 : zipWith (+) fibs tfibs
構文的な美しさではこれが究極かと思う。しかし意味論的にはすこし美しくない部分がある。
fibs, tfibs :: Integral n => [n]
のようにはできない。
fibs :: Integral n => [n]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
ならできる。しかし、この場合、キャッシュが効かなくなるのでO(2^n)となる。
型が一般的なほうが意味論的には美しいのだがメモ化されなくなってしまう。学問的にはどうなっているのだろう。コンパイルの段階でどうにかできそうな気がするが何か問題があるのだろうか。
「フィボナッチ数列の全体」ではなく「フィボナッチ数列のn番目」を求めるにはO(log n)のアルゴリズムがある(SICPより)。そっちの説明もあとで書こう。