Haskell - C栈溢出

Question

我刚刚被介绍给Haskell,所以我对如何使用该语言进行编码并不是很熟练,因此,如果这是重复的话,对不起,但是我不理解用该语言编写的其他代码.

我正在尝试编写一个算法,该算法将采用不超过给定值的正整数甚至整数的总和.我试图编写代码但是我一直在收到C堆栈溢出错误.

这是我的代码:

sumint :: Int -> Int
sumint x
  | x==0 = 0  
  | x==1 = 1
  | (x `mod` 2 == 0) && (x >= 2) = x + (sumint x-2)
  | (x `mod` 2 /= 0) && (x >= 1) = x + (sumint x-1)

我错在哪里得到这个错误？

Answer 1

初始错误:无限递归

单步执行代码:

sumint :: Int -> Int

嘿,类型签名.你摇滚.

sumint x
  | x==0 = 0

一个基础案例,很酷.

  | x==1 = 1

完全没必要的情况.好的,确定......除外.1甚至不是为什么我们将它包含在总和中？它应该为零(或完全删除).

  | (x `mod` 2 == 0) && (x >= 2) = x + (sumint x-2)

这个问题的关键在这里.X甚至很棒.2. X是正面的,是的.结果是x + (sumint x) - 2 不!

• 错误1:注意函数应用程序比运算符更严格,所以这应该是x + sumint (x-2).

这就是堆栈溢出的原因. sumint 2 == 2 + (sumint 2) - 2 + (sumint 2) -2 + (sumint 2) -2 + ...,yay无限递归.

  | (x `mod` 2 /= 0) && (x >= 1) = x + (sumint x-1)

另一种情况......赔率......积极......但为什么我们加入x？你想添加平均值,而不是赔率.因此,在我们得到的同时解决上述问题:

• 错误2:如果您确定x是奇数,请不要添加x.只是用sumint (x-1).

那你就没有了.如果x不是正数,会发生什么？你需要(另一个)案例.

| otherwise = 0

下一期:没有积累

现在的问题是你正在构建一个大的thunk(未评估的计算),而不是通过在进展时累积结果来在恒定的空间中操作.请注意,如果我们扩展你的计算,比如6,我们得到:

sumint 6 = 6 + sumint (6-2) 
      = 6 + 4 + sumint (4-2)
      = 6 + 4 + 2 + sumint (2-2)
      = 6 + 4 + 2 + 0

你真的不希望将所有这些添加内容分开,最好传入一个累加器,例如:

sumint x = go x 0
 where
  go n accumulator
         | n <= 0    = accumulator
         | odd n     = go (n-1) accumulator
         | otherwise = go (n-2) (accumulator + n)

旁注:其他stackoverflow公民可能会提到使累加器严格,这是一个很好的形式.我不想通过这里的讨论分散当前提问者的注意力.注意使用优化-O2,就足够了.

惯用解决方案

以上所有解决方案都相当冗长.使用函数和累加器迭代列表的一般操作是一种类型fold.Fold是函数式编程中常见的众多高度优化的结构遍历之一.在这种情况下,"严格的左侧折叠"是典型的候选者(来自Data.List).那就是foldl''按照'惯例表示它是绝对的意味着它是严格的,而l手段是剩下的.

sumint n = foldl' (+) 0 [val | val <- [0..n], even val]

在这里,我们折叠在列表上以获得我们的总和.要创建感兴趣的列表,我们使用列表推导 - 首先枚举值0..n并跳过任何不符合谓词的值even.

我们可以通过使用sum逐步2 的函数和列表理解来进一步清理它并改进它,从而只给我们你想要的平均值:

sumint n = sum [0,2..n]

Answer 2

它是运算符优先级问题.在Haskell中,函数应用程序具有最高可能的优先级.因此,当你写作时sumint x - 2,即使你把它解释为sumint (x-2),Haskell也会把它解释为(sumint x) - 2.因此 - 你试图sumint x直接定义sumint x- 它只是堆积递归函数调用,直到堆栈溢出.如果要在函数应用程序之前评估减法,则需要添加显式括号.