algorithm - 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)

问题的核心就在这里。 1. X 是均匀的——很棒。 2. X 是正的，是的。结果是 x + (sumint x) - 2 不!

• 错误 1:注意函数应用程序绑定(bind)比运算符更紧密，因此这应该是 x + sumint (x-2)。

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

  | (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。折叠是函数式编程中常见的许多高度优化的结构遍历之一。在这种情况下，“严格左折叠”是典型的候选者(来自 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]