递归haskell和堆栈溢出

Question

作为一个相对较新的Haskell和函数式编程的人,主要来自Python背景,我想知道为什么以下函数会导致Haskell中的堆栈溢出,即使我使用非常低的数字,如4或5作为输入变量,而Python中完全相同的函数可以处理20及以上的整数而不会溢出.为什么会这样？

countStairs <0 = 0
countStairs 0 = 1
countStairs n = countStairs(n-1) + countStairs(n-2) + countStairs(n-3)

我已经阅读了关于Haskell和堆栈溢出的其他响应,这些响应解决了代码优化和解决特定溢出代码的问题,而我有兴趣理解这两种语言在这里如何处理递归的差异的具体原因,或更一般地说为什么Haskell代码导致堆栈溢出.

编辑:我没有包含完整的python代码,因为这是我在Stack Overflow中的第一个问题,我正在努力弄清楚如何让我的Python正确格式化(非常欢迎你们中的一些人,顺便说一句).在这里,格式不佳,但所有,但所写的Python与整数20一起正常工作,而我无疑可怜的Haskell没有.我编辑了Haskell代码,以显示我最初省略的相应代码.我以为我包含了相关的递归部分,但显然我省略了基本情况.不过,正如所写,我的Haskell堆栈溢出而我的Python没有,我仍然对学习原因感兴趣.虽然我不是来自编程背景,但我真的很喜欢学习Haskell而只是想学习更多.感谢那些试图解决这个问题的人,尽管我的问题不完整.

def countStairs(n):
    if n < 0:
        return 0
    elif n == 0:
        return 1
    else:
        return countStairs(n-1) + countStairs(n-2) + countStairs(n-3)

myint = int(raw_input("Please enter an integer: "))
print countStairs(myint)

Answer 1

添加终止条件的另一种方法是使用保护(这也解决了<= 2Corbin提到的条件:

countStairs n | n > 0 = countStairs(n-1) + countStairs(n-2) + countStairs(n-3)
              | otherwise = 1

更新

您更新的Haskell示例不起作用,因为您误解了模式匹配的工作原理.你期望它像一个守卫一样工作(看到你试图< 0在模式匹配中提供一个布尔表达式),但是,你的函数版本永远不会匹配(当你调用countStairs函数时).考虑这个例子:

countStairs < 0 = "Matched '< 0'"
countStairs   0 = "Matched '0'"
countStairs   n = "Matched n"

main = do
    putStrLn $ countStairs (-1)  -- outputs: "Matched n"
    putStrLn $ countStairs 0     -- outputs: "Matched 0"
    putStrLn $ countStairs 20    -- outputs: "Matched n"

这里有趣的是你的函数实际编译.要找出原因,请将上面的代码加载到ghci并输入:browse.这将为您提供您在此模块中定义的功能列表.你应该看到这样的东西:

(Main.<) :: Num a => t -> a -> [Char]
countStairs :: Num a => a -> [Char]
main :: IO ()

你有countStairs,main哪些都有意义.但你也得到了这个函数Main.<.这是什么？您已重新定义了<此模块中的功能!如果你不熟悉,你可以定义缀函数(如+,<,>等),就像这样:

infix <
a < b = True

-- also defined as
(<) a b = True

通常,您需要infix FUNCTION_NAME指示您的函数是中缀.但是..前奏已经定义<为一个中缀函数,因此,你不需要,而只是给出了你自己的定义<.

现在,让我们countStairs < 0 = "Matched '< 0'"像我们一样重新安排我们a < b,你得到这个:

(<) countStairs 0 = "Matched '< 0'"

在这个函数中,countStairs实际上是函数的第一个参数<.

这是另外一个例子来说明这一点.尝试1 < 0在ghci中运行(模块仍然加载).这是你会得到的:

*Main> 1 < 0

<interactive>:1:3:
    Ambiguous occurrence `<'
    It could refer to either `Main.<', defined at foo.hs:3:13
                          or `Prelude.<', imported from Prelude

通常情况下,你会得到False,但在这种情况下,ghci不知道它是否应该使用你的函数(因为<它只是一个常规函数,而不是特殊语法)或内置(Prelude)版本<.

长话短说...使用保护(或case,或if)进行布尔测试,而不是模式匹配.

Answer 2

不太熟悉haskell,但看起来没有终止条件.我相信这将继续接近负无穷大.

尝试类似的东西:

countStairs 0 = 1
countStairs n = countStairs(n-1) + countStairs(n-2) + countStairs(n-3)

这意味着countStairs(0)= 1.

如果你打算调用countStairs(n)|,你可能也需要担心否定 n <= 2.

Answer 3

使用这个:

countStairs n | n <= 0 = 1
countStairs n = countStairs(n-1) + countStairs(n-2) + countStairs(n-3)

在GHCi中给我这个:

?x. x ? countStairs 20
289329

......大约两秒钟 所以是的,Corbin似乎是正确的.