如何使用foldr在列表中相互添加变量？

Question

当给定一个列表 [x0, x1, x2, . . . , xn−1] 时，函数应该 return 列表 [y0, y1, y2, . . . , yn−1] 其中 y0 = x0, y1 = x0 + x1, ...

所以如果你有 [1,2,3] 作为输入，你会得到 [1,3,6] 作为输出

我不完全理解 foldr，所以也许我可以得到一些帮助来尝试弄清楚如何更改最后一行以获得正确答案。

scan :: [Integer] -> [Integer]
scan [] = []
scan [x] = [x]

scan (x:xs) = x : foldr (/y -> y (+) x) 0 (scan xs)

我最初的解决方案（有效）使用 map 函数。

scan :: [Integer] -> [Integer]
scan [] = []
scan [x] = [x]

scan (x:xs) = x : map (+x) (scan xs)

Answer 1

编辑，我添加了第一部分以更好地解决您的两个实现。

首先，使用 foldr 解决您的实施问题，这里有几点说明：

$> (+) 1 5
$> 6

传递给 foldr 的函数有两个参数，而您只在 lambda 中提供一个参数。如果你真的想忽略第二个，你可以使用 _ 而不是将它绑定到变量 (\x _ -> x).

我认为这个实现会让您陷入困境。请参阅下面的讨论，了解我对解决此问题的正确方法的看法。

注意：可以使用foldr（source）实现map，这是您可以使用[=19]的一种方式=] 在您的工作（第二个）实现中。

用 foldr 实现这个并不是最优的，因为顾名思义，它从右边折叠：

foldr1 (+) [1..5]
--is equivalent to:
(1+(2+(3+(4+5))))

如您所见，求和操作是从列表的尾部开始完成的，这不是您要找的。要完成这项工作，您必须 "cheat" 并反转您的列表两次，一次在折叠之前，一次之后：

scan = tail . reverse . foldr step [0] . reverse where
  step e acc@(a:_) = (e + a) : acc

您可以使用从左侧折叠的左侧折叠来改善此效果：

foldl1 (+) [1..5]
--is equivalent to:
((((1+2)+3)+4)+5)

然而，这仍然不理想，因为要保持累加器中元素的顺序相同，您将不得不使用 ++ 函数，这相当于二次时间复杂度功能。一个妥协是使用 : 函数，但是你仍然必须在折叠后反转你的累加器列表，这只是线性复杂度：

scan' :: [Integer] -> [Integer]
scan' = tail . reverse . foldl step [0] where
  step acc@(a:_) e = (e + a) : acc

这仍然不是很好，因为 reverse 增加了额外的计算。因此，理想的解决方案是使用 scanl1，作为奖励，它不需要您提供起始值（上面示例中的 [0]）：

scan'' :: [Integer] -> [Integer]
scan'' = scanl1 (+)

scanl1是根据scanl实现的，大致定义如下：

scanl f init list = init : (case list of
                      []   -> []
                      x:xs -> scanl f (f init x) xs)

因此你可以简单地做：

$> scanl1 (+) [1..3]
$> [1,3,6]

最后一点，您的 scan 函数不必要专门用于 Integer，因为它只需要一个 Num 约束：

scan :: Num a => [a] -> [a]

这甚至可能会导致性能提升，但这是我的能力结束的地方，所以我不会再进一步了:)

How to use foldr to add variables to each other in a list?