这些函数是否递归递归？

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作为值)用于标记是否已去除了发生.

在移除函数中,当部分结果通过递归调用向下传递时,列表被反转,在结束时列表没有第一次出现但是倒置,因此必须将其反转以作为结果返回.

Answer 1

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

是一个尾调用,但是last(h:t):result作为一个未经评估的thunk开始生活,所以它是一个(手动波浪)位,就像这些嵌套函数调用仍在堆栈中.

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

conca在第二个参数中是非严格的,因此在应用递归调用时不会对这些thunk进行求值conca.

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和使用两个函数,而不是测试布尔参数的单个函数:

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每个元素(二次方)要好得多.