algorithm - Haskell-代码日志

我刚刚被介绍给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)

我在哪里弄错了这个错误？

最佳答案

初始错误:无限递归

逐步执行代码:

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)的绑定(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

下一期:无累积

现在的问题是，您正在累积大量的重击(未经评估的计算)，而不是通过在进行过程中累积结果来在恒定的空间中进行操作。请注意，如果将您的计算扩展为例如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]

sumInt

algorithm - Haskell-代码日志