haskell - 成本敏感的折叠

Question

让我用一个例子来解释我所说的成本敏感折叠的意思:以任意精度计算 pi。我们可以使用 Leibniz formula (效率不高，但又好又简单)和这样的惰性列表:

pi = foldr1 (+) [(fromIntegral $ 4*(-1)^i)/(fromIntegral $ 2*i+1) | i<-[0..]]

现在，显然这个计算永远不会完成，因为我们必须计算无限列表中的每个值。但实际上，我不需要 pi 的确切值，我只需要它到某个指定的小数位数。我可以这样定义 pi':

pi' n = foldr1 (+) [(fromIntegral $ 4*(-1)^i)/(fromIntegral $ 2*i+1) | i<-[0..n]]

但是我需要传入什么值才能获得我想要的精度，这一点并不明显。我需要的是某种成本敏感的折叠，只要我达到所需的精度就会停止折叠。这样的折叠是否存在？

(请注意，在这种情况下，很容易看出我们是否达到了所需的精度。因为莱布尼茨公式使用了一个与每一项交替符号的序列，误差将始终小于下一项的绝对值序列。)

编辑:拥有成本敏感的折叠也可以考虑计算时间/功耗真的很酷。例如，鉴于我有 1 小时的计算时间和 10kW-hrs 的消耗，我想要最准确的 pi 值。但我意识到这将不再具有严格的功能。

Answer 1

我的建议是使用扫描而不是折叠。然后遍历结果列表，直到找到所需的精度。左扫描( scanl )的一个有用的特例是 iterate功能:

piList :: [Double]
piList =
    map (4*) .
    scanl (+) 0 .
    map recip .
    iterate (\x -> -(x + 2 * signum x)) $ 1

您现在可以遍历此列表。例如，您可能会检查某个精度的更改何时变得不可见:

findPrec :: (Num a, Ord a) => a -> [a] -> Maybe a
findPrec p (x0:x1:xs)
    | abs (x1 - x0) <= p = Just x0
    | otherwise          = findPrec p (x1:xs)
findPrec _ _ = Nothing