成本敏感的折叠

Question

让我用一个例子解释一下成本敏感折叠的含义:用任意精度计算pi.我们可以使用Leibniz公式(效率不高,但又好又简单)和懒惰的列表如下:

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]]

但是,根本不清楚我需要传递什么值以获得我想要的精度.我需要的是某种对成本敏感的折叠,只要达到所需的精度就会停止折叠.这样的折叠存在吗？

(注意,在这种情况下,很容易看出我们是否已达到所需的精度.因为Leibniz公式使用了一个与每个术语交替出现符号的序列,所以误差总是小于下一个术语的绝对值.序列.)

编辑:拥有对成本敏感的折叠也很酷,这也可以考虑计算时间/功耗.例如,我想要最准确的pi值,因为我有1小时的计算时间和10kW小时的花费.但我意识到这将不再具有严格的功能.

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

Answer 2

Haskell这样做的方法是生成一个更加准确的答案的无限列表,然后到达并获得具有正确准确度的答案.

import Data.List (findIndex)
pis = scanl (+) 0 [4*(-1)**i/(2*i+1) | i <- [0..]]
accuracies = zipWith (\x y -> abs (x-y)) pis (tail pis)
piToWithin epsilon = case findIndex (<epsilon) accuracies of
    Just n  -> pis !! n
    Nothing -> error "Wow, a non-terminating loop terminated!"