Haskell斐波那契，使用惰性评估

• Z时代
• 2024-01-10
• 分类：综合

示例

惰性评估意味着Haskell将仅评估需要其值的列表项。

基本的递归定义是：

f (0)  <-  0
f (1)  <-  1
f (n)  <-  f (n-1) + f (n-2)

如果直接评估，它将非常缓慢。但是，假设我们有一个记录所有结果的列表，

fibs !! n  <-  f (n)

然后

                  ┌──────┐   ┌──────┐   ┌──────┐
                  │ f(0) │   │ f(1) │   │ f(2) │
fibs  ->  0 : 1 : │  +   │ : │  +   │ : │  +   │ :  .....
                  │ f(1) │   │ f(2) │   │ f(3) │
                  └──────┘   └──────┘   └──────┘
                  ┌────────────────────────────────────────┐
                  │ f(0)   :   f(1)   :   f(2)   :  .....  │ 
                  └────────────────────────────────────────┘
      ->  0 : 1 :               +
                  ┌────────────────────────────────────────┐
                  │ f(1)   :   f(2)   :   f(3)   :  .....  │
                  └────────────────────────────────────────┘

编码为：

fibn n = fibs !! n
    where
    fibs = 0 : 1 : map f [2..]
    f n = fibs !! (n-1) + fibs !! (n-2)

甚至

GHCi> let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
GHCi> take 10 fibs
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

zipWith通过将给定的二进制函数应用于给定的两个列表的相应元素来创建列表，因此zipWith (+) [x1, x2, ...] [y1, y2, ...]等于[x1 + y1, x2 + y2, ...]。

编写的另一种方式fibs是使用scanl函数：

GHCi> let fibs = 0 : scanl (+) 1 fibs
GHCi> take 10 fibs
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

scanl构建foldl将产生的部分结果的列表，沿着输入列表从左到右工作。即scanl f z0 [x1, x2, ...]等于[z0, z1, z2, ...] where z1 = f z0 x1; z2 = f z1 x2; ...。

多亏了惰性求值，这两个函数都定义了无限列表，而没有完全计算出来。也就是说，我们可以编写一个fib函数，以检索无界斐波那契序列的第n个元素：

GHCi> let fib n = fibs !! n  -- (!!) being the list subscript operator
-- or in point-free style:
GHCi> let fib = (fibs !!)
GHCi> fib 9
34

以上是 Haskell斐波那契，使用惰性评估 的全部内容， 来源链接： utcz.com/z/321031.html