4

我正在学习尾递归，并且在确定我的函数是否是尾递归时遇到了一些困难（主要是在我使用另一个函数的函数上）。

我已经实现了以下两个函数，但我不确定它们是否是尾递归的。

第一个是连接两个列表的函数。

conca list [] = list
conca [] result = result
conca (h:t) result = conca (init (h:t)) ( last(h:t):result ) 

concatenate::[a]->[a]->[a]
concatenate list1 list2 = conca list1 list2

函数中的计算在递归调用之前处理，但它使用 last 和 init，它们不是尾递归（我在http://ww2.cs.mu.oz.au/172/Haskell/tourofprelude中检查了它们的定义.html )

第二个功能是删除给定列表中给定数字的第一次出现。

invert [] result = result
invert (h:t) result = invert t (h:result)

remov n [] aux result = invert result []
remov n (h:t) aux result
        | aux==1 = remov n t 1 (h:result)
        | n==h = remov n t 1 (result)
        | otherwise = remov n t 0 (h:result)

remove n list = remov n list 0 []

参数 aux （可以假定 0 或 1 作为值）用于标记是否已删除出现。

在 remove 函数中，当部分结果通过递归调用向下传递时，列表被反转，最后列表没有第一次出现而是倒置，因此它必须被反转才能作为结果返回。

4

1 回答 1

6 
conca (h:t) result = conca (init (h:t)) ( last(h:t):result )

是一个尾调用，但last(h:t):result作为一个未评估的重击开始生命，所以它有点像这些嵌套函数调用仍然在堆栈上。

conca模式匹配其第一个参数，因此init将在递归调用中进行评估。

conca在其第二个参数中是非严格的，因此在应用conca.

remov是尾递归的，是的，但是....

使用TrueandFalse而不是0and1使您的代码更清晰：

remov n [] found result = invert result []
remov n (h:t) found result
        | found = remov n t True (h:result)
        | n==h = remov n t True (result)
        | otherwise = remov n t False (h:result)

remove n list = remov n list False []

最好不要传递这么多数据，减少复制n和使用两个函数，而不是测试布尔参数的单个函数：

remove' n list = seek list [] where
   seek []     result = invert result []
   seek (h:t) result | h == n    = got t result
                     | otherwise = seek t (h:result)
   got []    result = invert result []
   got (h:t) result = got t (h:result)

但got a result只是计算reverse result ++ a，所以你可以写

remove'' n list = seek list [] where
   seek []     result = invert result []
   seek (h:t) result | h == n    = invert result [] ++ t
                     | otherwise = seek t (h:result)

然而，这一切似乎相当费劲，并且仍然遍历列表两次。为什么不进行非尾调用：

removeFast n [] = []
removeFast n (h:t) | h == n = t
                   | otherwise = h:removeFast n t

t这样做的好处是立即生成其第一个元素，而不是运行整个列表，并且一旦找到要删除的元素，快捷方式无需进一步计算即可返回。尝试比赛length (removeFast 1 [1..100000])（length (remove 1 [1..100000])根据您的处理器速度改变零的数量）。

如果您想进行更有效的尾递归conca，可以使用以下技巧remove：

conc this result = prepend (invert this []) result

prepend [] result = result
prepend (h:t) result = prepend t (h:result)

和以前一样，您要遍历this两次，一次遍历invert它，另一次遍历它，但这仍然是一种线性算法，并且比对每个元素使用和prepending要好得多，后者是二次的。initlast

于 2012-12-19T02:55:56.843 回答