4

让我用一个例子来解释一下我所说的对成本敏感的折叠是什么意思：以任意精度计算 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]]

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

（注意，在这种情况下，很容易看出我们是否已经达到了要求的精度。因为莱布尼茨公式使用了一个与每一项交替符号的序列，所以误差总是小于下一项的绝对值。序列。）

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

4

4 回答 4

10

我的建议是使用扫描而不是折叠。然后遍历结果列表，直到找到所需的精度。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
于 2012-08-01T20:26:27.260 回答
4

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!"
于 2012-08-01T20:21:42.723 回答
2

在一般情况下，您要求的折叠不存在。您必须自己提供准确度估计。一般来说，这可能是个问题，但所有实际有用的序列确实对部分和的数值准确性有一个合理的上限，通常由其他人获得。但是，我应该鼓励您阅读相关的教科书，例如数值分析教科书，其中通常有部分关于估计无限数字序列的总和并对其进行上估计。

然而，有一个一般规则，如果数值过程有极限，那么数值位移会以粗略的几何级数趋近于零，因此如果两个后续位移是 1.5 和 1.0，那么接下来的位移将是大约 0.6，依此类推（最好在最后几个成员列表中累积这样的估计，而不仅仅是 2 个成员）。使用此规则和等式计算几何级数之和，您通常可以找到数值精度的合理估计。注意：这是经验法则（它有名字，但我忘记了），而不是严格的定理。

此外，IEEE Double/Float 的表示精度有限，并且在某些时候从序列尾部添加少量数字不会改变计算的部分总和。对于这种情况，鼓励您阅读 x86 中的浮点表示，您可能会发现自己的折叠。

总结：一般没有解决方案，但通常在实践中对最有用的序列有合理的估计，通常从文献中获得每种序列类型或硬件的数值限制

于 2012-08-01T20:32:36.473 回答
1

Daniel Wagner上面建议的一些很好的例子可以在论文Why Functional Programming Matters中找到

论文中的具体例子有：迭代求根、数值微分和数值积分。

于 2012-08-02T17:37:27.757 回答