fold{l|r} and short-circuit evaluation

Graham Klyne gk at ninebynine.org
Tue Oct 14 18:05:03 EDT 2003


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.

Is there a standard method for dealing with cases like this?

(I ask out of curiosity rather than need:  for my real application, I am 
using relatively short list with quite expensive combining operations, so I 
think the 'foldl' variant which doesn't actually examine list elements once 
the result is known, will work quite well for me.)

#g
--


-- Spike-allsame.hs
--
-- Test use of folding functions to evaluate whether all members
-- of a list are the same.
--
-- What I'm really interested in is whether the list gets evaluated
-- beyond what is needed to obtain the desired result.
--

import Maybe ( Maybe(..), isJust )

test allSame = and
     [ test1 allSame
     , test2 allSame
     , test3 allSame
     , test4 allSame
     , test5 allSame
     , test6 allSame
     , test7 allSame
     ]

test1 allSame = allSame [1,1,1,1]         == True
test2 allSame = allSame [1,2,3,4]         == False
test3 allSame = allSame [1,2,undefined,4] == False
test4 allSame = allSame [1]               == True
test5 allSame = allSame []                == True
test6 allSame = allSame [1,2,undefined]   == False
test7 allSame = allSame (1:2:repeat 3)    == False

testand = and (True:True:False:repeat True)

longList :: [Int]
longList = (1:2:repeat 3)

allSame1 :: (Eq a) => [a] -> Bool
allSame1 []     = True
allSame1 [_]    = True
allSame1 (a:as) = isJust $ foldr nextSame1 (Just a) as

nextSame1 :: (Eq a) => a -> Maybe a -> Maybe a
nextSame1 _  Nothing  = Nothing
nextSame1 a1 (Just a)
     | a1 == a   = Just a
     | otherwise = Nothing

{-
foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

foldr nextSame (Just 1) [2,undefined,4]
  ..>  nextSame 2 (foldr nextSame (Just 1) [undefined,4])
  ..>  nextSame 2 (nextSame undefined (foldr nextSame (Just 1) [4]))
  ..>  nextSame 2 (nextSame undefined (nextSame 4 (foldr nextSame (Just 1) 
[])))
  ..>  nextSame 2 (nextSame undefined (nextSame 4 ((Just 1))))
-}


allSame2 :: (Eq a) => [a] -> Bool
allSame2 []     = True
allSame2 [_]    = True
allSame2 (a:as) = isJust $ foldl nextSame2 (Just a) as

nextSame2 :: (Eq a) => Maybe a -> a -> Maybe a
nextSame2 Nothing  _ = Nothing
nextSame2 (Just a) a1
     | a1 == a   = Just a
     | otherwise = Nothing

{-
foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

foldl nextSame (Just 1) [2,undefined,4]
  ..>  foldl nextSame (nextSame (Just 1) 2) [undefined,4]
  ..>  foldl nextSame (nextSame (nextSame (Just 1) 2) undefined) [4]
  ..>  foldl nextSame (nextSame (nextSame (nextSame (Just 1) 2) undefined) 
4) []
  ..>  (nextSame (nextSame (nextSame (Just 1) 2) undefined) 4)
-}



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



More information about the Haskell-Cafe mailing list