Haskell 尾递归函数的效率

Question

我有以下基本 Haskell 代码：

prodsum x = prod x + sum x 

prod 0 = 1
prod n = n * prod (n-1)

sum 0 = 0
sum n = n + sum (n-1)

谁能解释一下为什么下面的代码更有效：

prod' n = prodTR n 1
   where prodTR 0 r = r
         prodTR n r = prodTR (n-1) $! (r*n)

sum' n = sumTR n 0
   where sumTR 0 r = r
         sumTR n r = sumTR (n-1) $! (r+n)

prodsum' n = prod' n + sum' n

Answer 1

让我们以sum为例。假设您使用 5

调用它

sum 5 = 5 + (sum 4)
      = 5 + (4 + sum 3)
      = 5 + (4 + (3 sum 2))
      = 5 + (4 + (3 + (2 + (sum 1))))
      = 5 + (4 + (3 + (2 + (1 + sum 0))))
      = 5 + (4 + (3 + (2 + (1 + 0))))
      = 5 + (4 + (3 + (2 + 1)))
      = 5 + (4 + (3 + 3))
      = 5 + (4 + 6)
      = 5 + 10
      = 15

直到 sum 0 被评估，其余的函数不能从内存中退出，因为它们都在等待对 return 的递归调用，以便它们可以 return 一个值。在这种情况下，它只是 5，想象一下 100000。

但是，sum' 会这样计算

sum' 5 = sumTR 5 0
       = sumTR 4 (0 + 5)
       = sumTR 4 5
       = sumTR 3 (5 + 4)
       = sumTR 3 9
       = sumTR 2 (9 + 3)
       = sumTR 2 12
       = sumTR 1 (12 + 2)
       = sumTR 1 14
       = sumTR 0 (1 + 14)
       = sumTR 0 15
       = sumTR 2 (9 + 3)
       = 15

此处，对 sumTR return 的调用是调用另一个函数的结果。因此，当前函数不必在内存中，因为它的 return 值不依赖于递归调用的结果（它不依赖于递归调用的结果，而是依赖于当前函数的 return 值与递归函数调用的return值的结果相同。

编译器通常会优化循环的尾部调用，因此它们非常高效。

阅读更多关于 Tail Recursion in this wiki page

正如 Carl 在评论中提到的，理解 $! 的作用很重要。它将功能的正常应用强制为功能的严格应用。这是什么意思？ $! 基本上将表达式简化为 Head 范式。什么是头部范式？表达式将被简化，直到它成为函数应用程序或数据构造函数。

考虑一下

sumTR (n-1) $ (r+n)

这里 r + n 将在 sumTR 函数被调用后被评估，就像我在上面的扩展中显示的那样。因为 Haskell 懒惰地评估一切。但是，您可以强制 r + n 的计算发生在函数调用之前，并使用 r + n 的结果调用它。这将带来巨大的运行时优势，因为如果必须进行模式匹配，编译器不必等到调用确定要调用的函数表达式。例如，

func :: Int -> Int
func 0 = 100
func a = a + a

在这里，如果我调用 func，像这样

func $ (1 - 1)

Haskell 在实际调用 func 之前不会计算 1 - 1。因此，在调用 func 之后，它将计算表达式并发现它是 0 并且它将选择 func 0 = 100 和 return 100。但是我们可以强制严格应用，像这样

func $! (1 - 1)

现在，haskell 将首先计算 (1 - 1)，然后它会知道该值为 0。因此，它将直接调用 func 0 = 100 和 return 100。我们通过强制严格应用来减轻编译器的负担。

您可以在 this haskell wiki page.

中阅读有关此严格应用程序的更多信息

Haskell 尾递归函数的效率

Efficiency of Haskell Tail-recursive functions

haskell

recursion

tail-recursion