CODEWITHSUNDEEP
haskell
Sawyer
Sawyer

Reputation: 15917

Haskell filter function laziness

Given:

take 5 (filter p xs)

say if filter p xs would return 1K match, would Haskell only filter out 5 matches and without producing a large intermediate result?

Upvotes: 3

Views: 613

Answers (3)

chi
chi

Reputation: 116139

It will scan xs only as much as needed to produce 5 matches, evaluating p only on this prefix of xs.

To be more precise, it can actually perform less computation, depending on how the result is used. For instance,

main = do
   let p x = (x==3) || (x>=1000000)
       list1 = [0..1000000000]
       list2 = take 5 (filter p list1)
   print (head list2)

will only scan list1 until 3 is found, and no more, despite take asking for five elements. This is because head is demanding only the first of these five, so laziness causes to evaluate just that.

Upvotes: 4

Jon Mountjoy
Jon Mountjoy

Reputation: 4526

"Would return 1K matches" under what circumstances?

Haskell doesn't work by first evaluating filter p xs (as you would in an ordinary call-by-value language like Java or Ruby). It works by evaluating take 5 first (in this case). take 5 will evaluate enough of filter p xs to end up with a result, and not evaluate the rest.

Upvotes: 4

Lee Duhem
Lee Duhem

Reputation: 15121

Yes, it will not.

If it does, something like the following would not work anymore

take 5 (filter (> 10) [1..])

This feature is called Lazy evaluation.

Upvotes: 2

Related Questions