haskell - 这些函数是尾递归的吗？

Question

我正在学习尾递归，但在确定我的函数是否是尾递归时遇到了一些困难(主要是我使用另一个函数的函数)。

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

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

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 函数中，当部分结果通过递归调用向下传递时，列表正在反转，最后列表没有第一次出现而是颠倒，因此必须将其反转才能作为结果返回。

Answer 1

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

是尾调用，但是 last(h:t):result以一个未评估的 thunk 开始生命，所以它有点像这些嵌套函数调用仍然在堆栈上。
conca模式匹配它的第一个参数，所以 init将在递归调用中进行评估。
conca在它的第二个参数中是非严格的，所以在应用 conca 的递归调用时，这些 thunk 不会被评估。 .
remov是尾递归的，是的，但是......

使用 True和 False而不是 0和 1使您的代码更清晰:

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并使用两个函数而不是测试 bool 参数的单个函数:

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它，但这仍然是一个线性算法，比使用 init 好得多和 last对于每个元素，它是二次的。