这个尾递归Haskell函数的错误在哪里？

Question

我必须以两种方式在Haskell中实现sum函数.一个函数具有尾递归,另一个函数没有尾递归.

这是没有尾递归的那个,它完美地工作

sum1 x = if x==0 then 0 else x + sum1(x-1)

这是我的尾递归尝试,它不起作用:

sum2 x = help 0 y
help x y = if y==0 then x else help(x+y,y-1)

有人可以指出错误吗？

Answer 1

你的路线:

help x y = if y==0 then x else help(x+y,y-1)

不是调用函数的正确语法.因为这里Haskell编译器会将其解释为:

help x y = if y==0 then x else help (x+y,y-1)
--                                  ^ a tuple

相反,你应该写:

help x y = if y==0 then x else help (x+y) (y-1)
--                                  ^ two arguments

此外,您还可以使用警卫,例如:

helper x y | y == 0 = x
           | otherwise = help (x+y) (y-1)

最后,第一行还有一个错误sum2.它应该是x代替y:

sum2 x = help 0 x

所以我们得到:

sum2 x = help 0 x
helper s x | x == 0 = s
           | otherwise = help (s+x) (x-1)

我也在to 和to (在um中)重命名y,helper以减少混乱(感谢@Bergi对此进行评论).xxss

或者使用eta减少:

sum2 = help 0

最后请注意,您不需要递归.可以更快地运行的实现如下:

sum3 x = div (x*(x+1)) 2

以来:

 n
---
\       (n+1) n
/   i = -------
---        2
i=1