Haskell:foldl'累加器参数

我一直在问一些关于严格性的问题，但我想我以前没有问过这个问题。希望这是更精确的。

假设我们有:

n = 1000000
f z = foldl' (\(x1, x2) y -> (x1 + y, y - x2)) z [1..n]

不改变 f ，我应该设置什么

z = ...

所以f z 不会溢出堆栈？ (即，无论 n 的大小如何，都在恒定空间中运行)

如果答案需要 GHC 扩展，那没关系。

我的第一个想法是定义:

g (a1, a2) = (!a1, !a2)

然后

z = g (0, 0)

但我不认为 g 是有效的 Haskell。

最佳答案

所以你的严格 foldl' 只会在折叠的每一步评估你的 lambda 的结果到弱头范式，即它只在最外层的构造函数中是严格的。因此元组将被评估，但是元组内的那些添加可能会作为 thunk 建立。这个 in-depth answer 实际上似乎解决了你在这里的确切情况。

W/R/T your g :您正在考虑 BangPatterns 扩展，它看起来像

g (!a1, !a2) = (a1, a2)

并将 a1 和 a2 计算为 WHNF，然后将它们返回到元组中。

你要关心的不是你的初始累加器，而是你的 lambda 表达式。这将是一个不错的解决方案:

f z = foldl' (\(!x1, !x2) y -> (x1 + y, y - x2)) z [1..n]

编辑 :在注意到你的其他问题后，我发现我没有仔细阅读这个问题。可以这么说，您的目标是拥有“严格的数据”。然后，您的另一个选择是创建一个新的元组类型，在其字段上具有严格性标签:

data Tuple a b = Tuple !a !b

然后，当您对 Tuple a b 进行模式匹配时，将评估 a 和 b。

无论如何，您都需要更改您的功能。

关于Haskell:foldl'累加器参数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11111642/