fold{l|r} and short-circuit evaluation

Graham Klyne gk at ninebynine.org
Wed Oct 15 12:11:53 EDT 2003


At 00:42 15/10/03 -0400, Derek Elkins wrote:
> > 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.

Ah, thanks :-O  That's a usefully concise statement of the problem I was 
bumping up against.  (I also note that foldr in this case messes up the 
order that operands are applied if the function is non-commutative or 
non-associative, and foldr1 places other constraints on the type.)

>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).

Perfect.  foldM is just what I was looking for.  The corresponding code is:

[[
allSame3 :: (Eq a) => [a] -> Bool
allSame3 []     = True
allSame3 (a:as) = isJust $ foldM nextSame3 a as

nextSame3 :: (Eq a) => a -> a -> Maybe a
nextSame3 a a1
     | a1 == a   = Just a
     | otherwise = Nothing
]]

And it does work in the infinite list case.

#g


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



More information about the Haskell-Cafe mailing list