Evaluation of list-comprehensions in Haskell

1
votes

I am wondering exactly how list-comprehensions are evaluated in Haskell. After reading this Removing syntactic sugar: List comprehension in Haskell and this: Haskell Lazy Evaluation and Reuse I still don't really understand if

[<function> x|x <- <someList>, <somePredicate>]

is actually exactly equivalent (not just in outcome but in evaluation) to

filter (<somePredicate>) . map (<function>) $ <someList>

and if so, does this mean it can potentially reduce time complexity drastically to build up the desired list with only desired elements? Also, how does this work in terms of infinite lists? To be specific: I assume something like:

[x|x <- [1..], x < 20]

will be evaluated in finite time, but how "obvious" does the fact that there are no more elements above some value which satisfy the predicate need to be, for the compiler to consider it? Would

[x|x <- [1..], (sum.map factorial $ digits x) == x]

work (see project Euler problem 34 https://projecteuler.net/problem=34). There is obviously an upper bound because from some x on x*9! < 10^n -1 always holds, but do I need to supply that bound or will the compiler find it?

2
haskelllist-comprehension
evaluation of [x|x <- [1..], x < 20] would not terminate so I don't know what you mean by how it 'will be just fine'. No attempt to reason about the predicate is done at all. – Lee
@Lee: I suppose you can take up to 19 elements from [x | x <- [1..], x < 20] safely, and after that an attempt to find another element matching the predicate never terminates. – 9000
I mean are the filter (p) . map (f) $ list and [f x|x <- list, p] evaluated the same way or is it possible for the compiler to do optimizations better in one than the other? – Chris
A list comprehension desugars to monadic code (using the guard function), not a composition of filter and map. – chepner
@epsilonhalbe: I think filter (< finiteNumber) ([1..] ++ [1]) should give a list of length finiteNumber, however I understand now that it will not. Thank you guys. – Chris

2 Answers

3
votes

There's nothing obvious about the fact that a particular infinite sequence has no more elements matching a predicate. When you pass a list to filter, it has no way of knowing any other properties of the elements than that an element can be passed to the predicate.

You can write your own version of Ord a => List a which can describe a sequence as ascending or not, and a version of filter that can use this information to stop looking at elements past a particular threshold. Unfortunately, list comprehensions won't use either of them.

Instead, I'd use a combination of takeWhile and a comprehension without a predicate / a plain map. Somewhere in the takeWhile arguments, you will supply the compiler the information about the expected upper bound; for a number of n decimal digits, it would be 10^n.

3
votes
[<function> x|x <- <someList>, <somePredicate>]

should always evaluate to the same result as

filter (<somePredicate>) . map (<function>) $ <someList>

However, there is no guarantee that this is how the compiler will actually do it. The section on list comprehensions in the Haskell Report only mentions what list comprehensions should do, not how they should work. So each compiler is free to do as its developers find best. Therefore, you should not assume anything about the performance of list comprehensions or that the compiler will do any optimizations.