memorized Fibonacci sequence

2023-12-25

今天在Codewars刷到一题，看到一个人的解答很巧妙。

众所周知，下面这段求斐波那契数列的代码很慢：

fibonacci :: Int -> Integer
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibonacci (n-1) + fibonacci (n-2)

我们可以转成迭代的方式或者使用记忆化搜索。

这是我从SICP的3.5节学到的，利用惰性求值算自然数数列：

nat :: [Int]
nat  = 0:map (+1) nat

ok，你已经学会了怎么求自然数数列，接下来算斐波那契数列吧：

fib :: Int -> [Int]
fib = 0:1:zipWith (+) fib (tail fib)

但是能不能在保留树形递归的同时进行记忆化搜索呢？

下面这段代码我觉得非常巧妙：

fibonacci :: Int -> Integer
fibonacci = (map fib' [0..] !!)
  where
		fib' 0 = 0
		fib' 1 = 1
		fib' n = fibonacci (n - 1) + fibonacci (n - 2)

以我对Haskell的浅薄理解，我证明不了上述代码有记忆化搜索的性质，希望有高手能教教我。

但是速度肯定是快多了，毕竟Haskell Wiki上是这样说的。

（ok，这个月的博客糊弄完了！）

Tags: #Haskell