在Haskell中计算列表的累加和

Question

编写一个函数，返回列表的累加和。例如，running [1,2,3,5]是 [1,3,6,11]。我编写了下面的函数，只能返回列表中所有值的最终和。那么如何将它们逐个分开？

sumlist' xx=aux xx 0
    where aux [] a=a
          aux (x:xs) a=aux xs (a+x)

- CathyLu

Answer 1

我认为你想要结合scanl1和(+)，做类似下面这样的事情：

scanl1 (+) *your list here*

scanl1将给定函数应用于列表，并将每个中间值报告到返回的列表中。

例如，为了在伪代码中写出它，

scanl1 (+) [1,2,3]

将输出一个类似以下列表：

[a, b, c] where { a = 1, b = a+2, c = b+3 }

换句话说，

[1, 3, 6]

Learn You A Haskell提供了很多有关Haskell中扫描、折叠等内容的精彩例子和描述。

希望这可以帮到你。

- Zach L

Answer 2

你可以通过在每一步前附加a+x并使用空列表作为基本情况，来调整您的函数以生成一个列表：

sumlist' xx = aux xx 0
    where aux [] a = []
          aux (x:xs) a = (a+x) : aux xs (a+x)

然而，用fold或scan表达这种情况更符合Haskell的习惯。

- sepp2k

---

aux (x:xs) a = a `seq` (a+x) : aux xs (a+x)。请仅返回已翻译的文本。 - Will Ness

Answer 3

尽管scanl1显然是“规范”的解决方案，但看看如何使用foldl来解决问题仍然具有启示意义：

sumList xs = tail.reverse $ foldl acc [0] xs where 
  acc (y:ys) x = (x+y):y:ys

或者点分风格：

sumList = tail.reverse.foldl acc [0] where 
  acc (y:ys) x = (x+y):y:ys

这里有一个丑陋的暴力方法：

sumList xs = reverse $ acc $ reverse xs where
  acc [] = []
  acc (x:xs) = (x + sum xs) : acc xs

有一个可爱但不太高效的解决方案，使用inits函数：

sumList xs = tail $ map sum $ inits xs

再次提到无参量函数：

sumList = tail.map sum.inits

- Landei

---

@sepp2k：如果你从列表的右侧开始，如何得到左侧元素的总和？ - Landei

@Lamdei：抱歉，我当时想错了。然而不懒仍然是不使用foldl（或您的暴力方法）的好理由。 - sepp2k

为什么要使用 reverse？在正向方向上，sumList = (\snd` []) . foldl (\(a, k) x -> (a+x, k . (a+x:))) (0, id)` 可以正常工作。 - ephemient

@ephemient：很酷，我没有想到过，但对于初学者来说可能太复杂了。 - Landei

@ephemient 您的代码片段重新实现了 scanl1 (+)，但它会在返回之前强制处理整个输入列表的结构，所以无法用于无限列表。 （是啊，十年过去了... :)) - Will Ness

Answer 4

与另一个问题相关，我发现了这种方法：

rsum xs = map (\(a,b)->a+b) (zip (0:(rsum xs)) xs)

我认为它甚至相当高效。

- Florian F

---

map (uncurry f) $ zip xs ys == zipWith f xs ys，因此该函数为 rsum xs = zipWith (+) (0:(rsum xs)) xs，但它没有像应该的那样重复使用结果（因此是二次的），像下面这样就是线性的：rsum xs = rs where rs = zipWith (+) (0:rs) xs，或者 scanl1 (+) xs 也是线性的。 - Will Ness

Answer 5

我不确定这是否是规范的，但在我看来它很漂亮 :)

sumlist' [] = []
sumlist' (x:xs) = x : [x + y | y <- sumlist' xs]

- dmontaner

---

这是二次的。另见。 - Will Ness

Answer 6

正如其他评论所述，找到既线性又非严格的解决方案将是不错的。问题在于右折叠和扫描无法查看左侧的项，而左折叠和扫描都对输入列表进行严格操作。实现这一点的方法之一是定义我们自己的函数，该函数从右侧折叠但向左查看。例如：

sumList:: Num a => [a] -> [a]
sumList xs = foldlr (\x l r -> (x + l):r) 0 [] xs

定义foldr使其在列表中是非严格的并不太困难。请注意，它必须有两个初始值--一个从左边开始（0），一个从右边结束（[]）：

foldlr :: (a -> b -> [b] -> [b]) -> b -> [b] -> [a] -> [b]
foldlr f l r xs =
    let result = foldr (\(l', x) r' -> f x l' r') r (zip (l:result) xs) in
        result

- collideorscape

---

我不明白这个回答跟页面顶部的问题有什么关系，但是它应该会有用。请根据回答进行编辑或删除回答。否则它可能会被标记为“非回答”并被删除。 - Yunnosch

感谢Drazisil和Yunnosch。我已经编辑了我的回答，删除了问题并使其更清楚地回答了原始问题。 - collideorscape