时间戳

首页 > 解决方案 > 如何制作尾递归函数

list - 如何制作尾递归函数

问题描述

我对如何使函数“尾递归”感到非常困惑。

这是我的函数，但我不知道它是否已经是尾递归的。

我正在尝试在 Haskell 中合并两个列表。

merge2 :: Ord a =>[a]->[a]->[a]
merge2 xs [] = xs
merge2 [] ys = ys
merge2 (x:xs)(y:ys) = if y < x then y: merge2 (x:xs) ys else x :merge2 xs (y:ys)

标签： listhaskellrecursionmergetail-recursion

解决方案

您的函数不是尾递归的；它是递归的。但是，如果你想提高内存效率，你应该在 Haskell 中使用受保护的递归。

要使调用成为尾调用，其结果必须是整个函数的结果。此定义适用于递归和非递归调用。

例如，在代码中

f x y z = (x ++ y) ++ z

该调用(x ++ y) ++ z是尾调用，因为它的结果是整个函数的结果。该呼叫x ++ y不是尾随呼叫。

对于尾递归的示例，请考虑foldl：

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ acc []     = acc
foldl f acc (x:xs) = foldl f (f acc x) xs

递归调用foldl f (f acc x) xs是尾递归调用，因为它的结果是整个函数的结果。因此它是一个尾调用，并且它是foldl对自身的递归调用。

代码中的递归调用

merge2 (x:xs) (y:ys) = if y < x then y : merge2 (x:xs) ys 
                                else x : merge2 xs (y:ys)

不是尾递归的，因为它们没有给出整个函数的结果。调用的结果merge2用作整个返回值的一部分，即一个新列表。构造函数，而(:)不是递归调用，给出了整个函数的结果。事实上，懒惰会(:) _ _立即返回，并且_只有在需要时才会填补这些漏洞。这就是为什么受保护的递归是节省空间的。

然而，尾递归并不能保证惰性语言的空间效率。通过惰性求值，Haskell 在内存中构建thunk或结构来表示尚未求值的代码。考虑对以下代码的评估：

foldl f 0 (1:2:3:[])
=> foldl f (f 0 1) (2:3:[])
=> foldl f (f (f 0 1) 2) (3:[])
=> foldl f (f (f (f 0 1) 2) 3) []
=> f (f (f 0 1) 2) 3

您可以将惰性求值视为“由外而内”发生的事情。当递归调用foldl被评估时，thunk 会在累加器中建立。因此，使用累加器的尾递归在惰性语言中的空间效率不高，因为延迟评估（除非在进行下一次尾递归调用之前立即强制累加器，从而防止 thunk 积累，而是呈现已经-计算值，最后）。

您应该尝试使用受保护的递归，而不是尾递归，其中递归调用隐藏在惰性数据构造函数中。使用惰性求值时，表达式会被求值，直到它们处于弱头范式(WHNF) 中。表达式在 WHNF 中时是：

  • 应用于参数的惰性数据构造函数（例如Just (1 + 1)）
  • 部分应用的函数（例如const 2）
  • 一个 lambda 表达式（例如\x -> x）

考虑map：

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

map (+1) (1:2:3:[])
=> (+1) 1 : map (+1) (2:3:[])

由于数据构造函数的原因，表达式(+1) 1 : map (+1) (2:3:[])在 WHNF 中(:)，因此计算在此时停止。您的merge2函数还使用受保护的递归，因此它在惰性语言中也很节省空间。

TL;DR：在惰性语言中，如果尾递归在累加器中建立 thunk，它仍然会占用内存，而受保护的递归不会建立 thunk。

有用的网址：

推荐阅读