fold{l|r} and short-circuit evaluation
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
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
Scott Turner writes: : | 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 Once you do that, you can simplify the result type of the fold, from 'Maybe a' to Bool. allSame [] = True allSame (a:as) = all (a==) as
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
On Tue, 14 Oct 2003 17:05:03 +0100
Graham Klyne
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).
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
participants (4)
-
Derek Elkins -
Graham Klyne -
Scott Turner -
Tom Pledger