1

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

这似乎是正确的（但我可能错过了一些东西）。有没有更简单或更有效的方法来做到这一点，可能使用扫描？

4

2 回答 2

5

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

于 2021-09-16T01:09:46.083 回答
0

你的函数应该写成

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代码中的 不是“总数”，它只是输入中的下一个值 after x。所以这里需要名称中的一些对称性（命名很重要）。last xs因为调用，所以从不计算位，因此init可以是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)

正如评论中所述，您已经看到了。因此，它在计算上实际上等同于您的代码，这与另一个答案中的代码不同，后者通过实质上不同的、本质上是 二次的（并且不必要的）计算来计算相同的结果。

如果您真的想将zipWith (-)过程表达为展开，可以将其完成为

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

因为tails ~= iterate tail, 和迭代和展开本质上是一回事（每个都可以表示为另一个，有一些可能需要的预处理和/或后处理步骤）。

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

> 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'是一个非常小的区别。

你能发现吗？

除此之外，无论您的代码名义上使用foldror unfoldr，重要的是它是否足够懒惰。foldr具有惰性组合功能的代码同样能够编写. 像这样sum的变质必然是严格的。要将您的函数编写为适当的变形，使其仍然应该是线性的，我们需要通过压缩输入来预处理输入，tail因为我们一次需要两个头部元素。对此进行编码的另一种方法是使用paramorphism，以便我们可以访问输入的当前尾部及其当前元素。并且通过折叠（是的，就像正在做的那样）可以很容易地模拟拟态。tailsbaz

于 2021-09-24T12:26:04.553 回答