CODEWITHSUNDEEP
haskelllazy-evaluationstrictness
David Unric
David Unric

Reputation: 7719

How to set strictness in list comprehension?

I'm bit stuck how to rewrite following strict-evaluated list comprehension to use seq instead of bang pattern:

zipWith' f l1 l2 = [ f e1 e2 | (!e1, !e2) <- zip l1 l2 ]

Any idea ?

I've tried

zipWith' f l1 l2 = [ e1 `seq` e2 `seq` f e1 e2 | (e1, e2) <- zip l1 l2 ]

but this unfortunately does not force an evaluation to WHNF.

Upvotes: 2

Views: 778

Answers (3)

Derek Elkins
Derek Elkins

Reputation: 31

To explain the original poster's example and some of Don's noted behavior. Using (>>=) as a concise concatMap, the original example translates into:

zip l1 l2 >>= \(!e1, !e2) -> [f e1 e2]

The second example is:

zip l1 l2 >>= \(e1, e2) -> [e1 `seq` e2 `seq` f e1 e2]

But what the desugared first version actually further desugars into is:

zip l1 l2 >>= \(e1, e2) -> e1 `seq` e2 `seq` [f e1 e2]

e1 and e2 get forced when the concat in concatMap flattens these singleton lists which provides the "force as I go along" behavior.

While this isn't what one would normally think of as a "strict" zipWith, it is not a fluke that it works for the fibs example.

Upvotes: 3

augustss
augustss

Reputation: 23014

The essential thing you want the strict zipWith to do is to evaluate the elements of the list at the time the cons cell is forced. Your function does not do that. Just try

main = print $ length $ zipWith' undefined [1..10] [1..100]

It's a fluke of the strictness analysis when you use (+) that makes it work.

The function you want is something like this:

zipW f (x:xs) (y:ys) = let z = f x y in seq z (z : zipW f xs ys)
zipW _ _ _ = []

You cannot decouple the production of the cons cell from the production of the value, because the former should force the latter.

Upvotes: 5

Don Stewart
Don Stewart

Reputation: 137947

You can mechanically translate bang patterns into calls to seq following the GHC manual:

This:

zipWith' f l1 l2 = [ f e1 e2 | (!e1, !e2) <- zip l1 l2 ]

Becomes Too lazy:

zipWith' f l1 l2 =
    [ f e1 e2
    | e <- zip l1 l2
    , let t = case e of (x,y) -> x `seq` y `seq` (x,y)
    , let e1 = fst t
    , let e2 = snd t
    ]

Which is more concisely written as (too lazy):

zipWith' f l1 l2 =
    [ f e1 e2
    | e <- zip l1 l2
    , let (e1,e2) = case e of (x,y) -> x `seq` y `seq` (x,y)
    ]

Though I'd write it as (wrong, too lazy)

zipWith' f l1 l2 = zipWith (\x y -> uncurry f (k x y)) l1 l2
    where
        k x y = x `seq` y `seq` (x, y)

You could also move the strictness hint to a data structure:

data P = P !Integer !Integer

zipWith' f l1 l2 = [ f e1 e2 | P e1 e2 <- zipWith P l1 l2 ]

Or as:

zipWith' f l1 l2 = [ f e1 e2 | (e1, e2) <- zipWith k l1 l2 ]
    where
        k x y = x `seq` y `seq` (x,y)

Upvotes: 6

Related Questions