fold{l|r} and short-circuit evaluation

[Derek Elkins]

On Tue, 14 Oct 2003 17:05:03 +0100
Graham Klyne <gk at ninebynine.org> wrote:

> I'm trying to use foldl or foldr to run a computation over a list, in
> such a way that only as much of the list as may be needed is actually
> examined.
> 
> I believe the 'and' function behaves like this (e.g. see testand
> below), but when I use a function that performs pairwise operations on
> the list elementsa, it seems that I always end up constructing the
> entire list, even if I don't need to examine the value of each
> element.  I guess I could try and figure out my own 2-place folding
> function, but this seems as if there should be a common solution.
> 
> My test code is below.  The tests are evaluated as:
>      test allSame1
> or
>      test allSame2
> to use a foldl- or foldr-versions of the function respectively
> 
> If I comment out the indefinitely long list case (test7) in the
> definition of 'test', the foldl version will pass all these test cases
> and foldr throws an error on test6.  But if I include test7, using
> Hugs the foldr test case returns a C stack overflow, and the foldl
> case silently disappears.

foldl never works on infinite lists.
foldr isn't tail recursive, so you don't use it with strict functions if
you are expecting large input.  With lazy (in the second argument)
functions it's appropriate.
You may also want to look at foldM.  Instantiated for an exception-like
monad (Maybe,Either,etc.), you can effectively "throw" a result (or lack
thereof for Maybe).