fold{l|r} and short-circuit evaluation

Scott Turner p.turner at
Tue Oct 14 22:04:04 EDT 2003

On Tuesday 14 October 2003 12:05 pm, Graham Klyne 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.

Foldr is usually the way to go.  'and' works by folding the '&&' operator, 
which does not always evaluate its right operand.  Your nextSame1 produces 
different behavior because it always evaluates the right operand, at least to 
the point of whether it's 'Nothing' or not. But that requires that nextSame1 
be invoked again, etc.

> allSame1 (a:as) = isJust $ foldr nextSame1 (Just a) as

> nextSame1 _  Nothing  = Nothing
> nextSame1 a1 (Just a)

You could deal with this deficiency in two ways.  First, revise nextSame1 to 
return something like (a, Bool) so that you can compare values without having 
to determine whether the entire tail of the list is uniform.  Alternatively, 
since nextSame1 is called only in the context where the expected value is 
known, you could give it the expected value as another parameter.  Then it 
would be possible to sometimes avoid referencing the right operand at all. It 
would be called 
     foldr (nextSame1 a) (Just a) as

More information about the Haskell-Cafe mailing list