algorithm - 这种算法是否有一个通用名称，类似于running-sum-like算法？

Question

我正在寻找以下算法/算法技巧的通用名称。

xs = [0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1]

ys = [xs[0]]
for i in range(1, len(xs)):
  if xs[i] == 1:
    ys.append(ys[i - 1] + 1)
  else:
    ys.append(ys[i - 1])

print ys
# prints: [0, 1, 1, 1, 2, 2, 3, 4, 4, 4, 4, 5]

也就是说，累积在 中的某个索引处看到的 1 的数量xs。另外，有没有更简洁的方法来做到这一点？欢迎 Scala、Python 和 Haskell 回答。

Answer 1

在 Haskell 中，这可以写得更简洁，它被命名为 a scan（更准确地说是左扫描，因为它累积了左折叠的中间结果），

scanl1 (\y x -> y + if x == 1 then 1 else 0) xs

而且，对于运行总和，甚至更好，

scanl1 (+) xs

Answer 2

我不这么认为，对一个值进行累积总和太基本了。让代码保持原样，这是可以理解的。