具有保护尾部的函数是递归的

Question

我想知道带卫兵的功能是否可以尾递归.鉴于此实施elem例如

elem' :: (Eq a) => a -> [a] -> Bool
elem' x [] = False
elem' x (y:ys)
    | x == y       = True
    | otherwise    = elem' x ys

这个尾巴是递归的吗？我会说是的,但我不知道怎么说.

Answer 1

是的,它是尾递归的.

"尾递归"在Haskell上下文中的一个可能定义是对"连接点"的调用是有效的,因为它们可能只出现在尾递归位置.在Compiling without Continuations的第3页,我们找到了这个数字:

我们看到案例陈述中替代品的右侧是尾部调用头寸.我们还可以在GHC源中找到与此对应的代码.

根据Haskell报告中的守卫的消亡,它告诉我们守卫本质上是嵌套case表达式,我们可以得出结论,你的函数是尾递归的.

(虽然应该说" elem'作为两个参数的函数是尾递归的" - 没有指定arity,这个问题没有多大意义.)