fold{l|r} and short-circuit evaluation

[Graham Klyne]

At 21:04 14/10/03 -0400, Scott Turner wrote:
>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.

I was thinking that returning a (Maybe a) had a similar effect, but that 
wasn't working for me.

>   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

Yes!  That's something I was overlooking.  Thanks.  Tom's code (next 
message) is neat and suggests the sort of thing I was casting around for, 
but I think the key idea here is partially evaluating the test function.

Now I need to figure out of that works for my real application which is 
more complex.  I perform a complex computation using pairs list elements, 
trying to evaluate something like:

   [(Just a1) `bigmunge` a2 `bigmunge` a3 ... `bigmunge` an]

where bigmunge :: (Maybe a) -> a -> (Maybe a)
and   bigmunge Nothing _ = Nothing

so as soon as I get Nothing I need to look no further.  Unlike the 
simplified example I posted, I see no single value for partially evaluating 
the bigmunge function.

Hmmm... a simple recursive definition might look like this:

foldbigmunge :: [a] -> Maybe a
foldbigmunge  (a:as) = foldbigmunge1 (Just a) as

foldbigmunge1 :: (Maybe a) -> [a] -> Maybe a
foldbigmunge1 Nothing   _       = Nothing
foldbigmunge1 a         []      = a
foldbigmunge1 (Just a1) (a2:as) = foldbigmunge1 (a1 `bigmunge` a2) as

But I still struggle to see how it might be implemented using a normal fold.

(The "practical" part of me thinks "so what" -- I could just use a 
recursive form like that above, but I do wonder if I'm still missing a 
trick here.)

#g


------------
Graham Klyne
For email:
http://www.ninebynine.org/#Contact