title: Cost sensitive folds
body: <p>Let me explain what I mean by a cost-sensitive fold with an example: calculating pi with arbitrary precision.  We can use the <a href="http://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80" rel="nofollow">Leibniz formula</a> (not very efficient, but nice and simple) and lazy lists like this:</p>
  
  <pre><code>pi = foldr1 (+) [(fromIntegral $ 4*(-1)^i)/(fromIntegral $ 2*i+1) | i&lt;-[0..]]
  </code></pre>
  
  <p>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:</p>
  
  <pre><code>pi' n = foldr1 (+) [(fromIntegral $ 4*(-1)^i)/(fromIntegral $ 2*i+1) | i&lt;-[0..n]]
  </code></pre>
  
  <p>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?</p>
  
  <p>(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.)</p>
  
  <p>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.</p>