撤消前缀和

Question

在Haskell中计算前缀和的简单方法是

scanl1 (+) [1,2,3,4,5,6]

产生输出

[1,3,6,10,15,21]

我需要写逆，这就是我想出的：

undo_prefix_sum :: (Num a) => [a] -> [a]
undo_prefix_sum s = init $ snd $ 
    foldr (\cur (tot, l) -> (cur, (tot-cur):l)) 
          (last s, []) 
          (0:s)

这似乎是正确的（但我可能漏掉了什么）。是否有更简单或更有效的方法来执行此操作，可能使用扫描？

Answer 1

在我看来，prefix_sum更自然地表示为折叠，undo_prefix_sum更自然地表示为展开。

import Data.List

undo_prefix_sum  = unfoldr (\xs -> if null xs 
                                   then Nothing
                                   else let (h:t) = xs 
                                        in Just (h,  map (subtract h) t))

unfoldr 使用函数从种子值开始构建列表。在这种情况下，种子本身就是一个列表；我们在结果中使用种子的第一个元素，并将列表的其余部分（修改版本）作为种子来递归计算结果的其余部分。

Answer 2

你的函数应该写成

undo_prefix_sum' :: (Num a) => [a] -> [a]
undo_prefix_sum' xs = init $ snd $ 
    foldr (\x ~(y, ys) -> (x, (y-x):ys)) 
          (undefined, []) 
          (0:xs)

您代码中的 tot 不是“总计”，它只是 x 之后输入中的 next 值。所以这里需要名称中的一些对称性（命名很重要）。由于 init 调用，last xs 位永远不会被计算，因此可以只是 undefined，以避免给人以错误的印象。

因为它所做的只是计算每个元素与其前身之间的差异（或者 0 对于第一个元素），我们不妨清楚这一点：

foo xs = [y-x | i <- [0..length xs-1], let y=xs!!i ; x = (0:xs)!!i ]

当然是二次方，它计算出 length 这是一个大禁忌；但至少它很简单，所以它很容易修复：

bar xs = [y-x | x <- 0:xs | y <- xs]
       = map (uncurry (-)) $ zip xs (0:xs)
       = zipWith (-) xs (0:xs)

如评论中所述，您已经看到了。所以它在计算上确实等同于你的代码，不像另一个答案中的代码通过本质上不同的方法计算相同的结果，essentially quadratic（这是不必要的），计算。

如果你真的想把zipWith (-)过程表达为一个展开，可以这样

baz xs = [y-x | (x:y:_) <- tails (0:xs)]

因为tails ~= iterate tail，迭代和展开本质上是同一件事（每个都可以表示为另一个，可能需要一些预 and/or post- 处理步骤） .

最后一件事。您的代码确实有问题。这是不必要的严格：

> take 2 $ undo_prefix_sum $ [1,2] ++ undefined
*** Exception: Prelude.undefined

> take 2 $ undo_prefix_sum' $ [1,2] ++ undefined
[1,1]

foo 上面也同样严格。此答案中的所有其他版本（以及其他答案中的代码）都成功并正确地计算了结果。 undo_prefix_sum' 这里和你的代码之间的唯一区别，除了变量重命名之外，是一个非常小的区别。

你能发现吗？

除此之外，无论您的代码名义上使用 foldr 还是 unfoldr，重要的是它是否足够惰性。 foldr 具有惰性组合功能的编码能力与 that 一样。像 sum 这样的同质异形必然是严格的。要将您的函数编写为适当的变形使其仍然是线性的，因为我们需要同时使用两个头元素，因此我们需要通过使用 tail 压缩它来预处理输入。另一种编码方式是使用同构，这样我们就可以访问输入的当前尾部及其当前元素。通过折叠 tails 可以很容易地 emulated 实现同构（是的，就像 baz 所做的那样）。

撤消前缀和

Undoing a prefix sum

haskell

prefix-sum