CODEWITHSUNDEEP
haskelllazy-evaluation
cdk
cdk

Reputation: 6778

Why Isnt This Function Consuming Lazily?

I have two functions similar to filter and takeWhile.

filterAcc, takeWhileAcc :: ([a] -> Bool) -> [a] -> [a]
filterAcc p xs = go xs []
    where go [] acc     = acc
          go (x:xs) acc
            | p (x:acc) = go xs (x:acc)
            | otherwise = go xs acc

takeWhileAcc p xs = go xs []
    where go [] acc     = acc
          go (x:xs) acc
            | p (x:acc) = go xs (x:acc)
            | otherwise = acc

they both take predicates and lists, and they differ from the regular filter and takeWhile in that the predicates take the accumulated result as inputs.

my problem is that while filter even [1..] will start producing output immediately (lazily), filterAcc (any even) [1..] hangs. My suspicion is that the helper function go is preventing these functions from acting lazily.

How can i make these functions operate lazily?

Upvotes: 1

Views: 186

Answers (2)

Will Ness
Will Ness

Reputation: 71065

Lazy list consumption is usually achieved by foldr.

You need left-to-right information flow for your accumulator. This is usually achieved by using foldl, but that means strict list consumption.

The solution is to use scanl:

--- mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
--- scanl     :: (a   -> b -> a)        -> a   -> [b] -> [a]

takeWhileAcc p []     = []
takeWhileAcc p (x:xs) = map snd $ takeWhile (p.fst) 
                                $ scanl (\(acc,_) y-> (y:acc,y)) ([x],x) xs

filterAcc p []        = []
filterAcc p (x:xs)    = map snd $ filter (p.fst) 
                                $ scanl (\(acc,_) y-> (y:acc,y)) ([x],x) xs

Another possibility is to use until, or mapAccumL. The latter would be a natural fit, except that it doesn't collect the accumulated values, but rather passes along the last accumulator value.

Upvotes: 1

hammar
hammar

Reputation: 139840

The problem is that the cons case of go always ends in a tail call to itself. It only returns something useful when it's reached the end of the list, which of course never happens with an infinite list.

Instead, you should return elements as you go:

filterAcc, takeWhileAcc :: ([a] -> Bool) -> [a] -> [a]
filterAcc p xs = go xs []
    where go [] acc     = []
          go (x:xs) acc
            | p (x:acc) = x : go xs (x:acc)
            | otherwise = go xs acc

takeWhileAcc p xs = go xs []
    where go [] acc     = []
          go (x:xs) acc
            | p (x:acc) = x : go xs (x:acc)
            | otherwise = []

Upvotes: 6

Related Questions