Let me explain what I mean by a cost-sensitive fold with an example: calculating pi with arbitrary precision. We can use the Leibniz formula (not very efficient, but nice and simple) and lazy lists like this:
pi = foldr1 (+) [(fromIntegral $ 4*(-1)^i)/(fromIntegral $ 2*i+1) | i<-[0..]]
Now, obviously this computation will never complete because we must compute every value in the infinite list. But in practice, I don't need the exact value of pi, I just need it to some specified number of decimal places. I could define pi' like this:
pi' n = foldr1 (+) [(fromIntegral $ 4*(-1)^i)/(fromIntegral $ 2*i+1) | i<-[0..n]]
but it's not at all obvious what value for n I need to pass in to get the precision I want. What I need is some sort of cost-sensitive fold, that will stop folding whenever I achieve the required accuracy. Does such a fold exist?
(Note that in this case it is easy to see if we've achieved the required accuracy. Because the Leibniz formula uses a sequence that alternates sign with each term, the error will always be less than the absolute value of the next term in the sequence.)
Edit: It would be really cool to have cost-sensitive folds that could also consider computation time/power consumption. For example, I want the most accurate value of pi given that I have 1 hour of computation time and 10kW-hrs to spend. But I realize this would no longer be strictly functional.
My recommendation is to use a scan instead of a fold. Then traverse the resulting list, until you find the precision you want. A useful special case of the left scan (scanl
) is the iterate
function:
piList :: [Double]
piList =
map (4*) .
scanl (+) 0 .
map recip .
iterate (\x -> -(x + 2 * signum x)) $ 1
You can now traverse this list. For example you might check when the change to a certain precision becomes invisible:
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With