部分应用与模式匹配：为什么这些 Haskell 函数的行为不同？

Question

我试图了解有关 Haskell 函数的一些内容。

首先，这是一个以典型的“慢”方式定义的斐波那契函数（即没有记忆的递归，也没有无限列表技巧）

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

接下来，相同的规范记忆版本。（仅与教程/书籍/等中的典型示例略有不同，因为我更喜欢!!运算符的前缀版本。）

memfib = (!!) (map fib [0..])
  where
    fib 0 = 0
    fib 1 = 1
    fib k = memfib(k-2) + memfib(k-1)

上面的解决方案使用了!!运算符的部分应用，这是有道理的：我们希望memfib最终成为一个带参数的函数，并且我们正在定义它而不在定义中包含参数。

到现在为止还挺好。现在，我想我可以编写一个等效的记忆函数，在定义中包含一个参数，所以我这样做了：

memfib_wparam n = ((!!) (map fib [0..])) n
  where
    fib 0 = 0
    fib 1 = 1
    fib k = memfib_wparam(k-2) + memfib_wparam(k-1)

（拉姆达演算方面，memfib并memfib_wparams互为只是ETA-转换。我想???）

这有效，但记忆消失了。事实上，它的memfib_wparam表现甚至比showfib: 不仅慢，而且内存使用量增加了一倍多。）

*Main> slowfib 30
832040
(1.81 secs, 921,581,768 bytes)
*Main> memfib 30
832040
(0.00 secs, 76,624 bytes)
*Main> memfib_wparam 30
832040
(2.01 secs, 2,498,274,008 bytes)

这里发生了什么？更重要的是，我对 Haskell 函数定义出错的更广泛理解是什么？我假设我使用的语法memfib_wparam只是我所做的语法糖memfib，但显然它不是。

Answer 1

不同之处在于您的fib函数何时被绑定。

where-bound 定义可以访问外部函数的参数（即参数在 内的“范围内” where）。这意味着，fib应该有机会获得n，而这又意味着fib被定义后 n获得通过，这是一个不同的，其手段fib为每一个n，这是一个不同的呼叫，来map fib [0..]为每一个n。

如果您想 eta-expand 您的memfib，这将是“正确”的方法（即不会过度扩展 的范围n）：

memfib = \n -> theCache !! n
    where
        theCache = map fib [0..]

        fib 0 = 0 
        fib 1 = 1 
        fib k = memfib(k-2) + memfib(k-1)

如果您要与 lambda 演算进行比较，关键区别在于 eta-reduction/expansion 并没有说明性能，它只是保证程序的结果在逻辑上保持不变。它的作用。