1

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?

Community
  • 1
  • 1
Chris
  • 710
  • 7
  • 15
  • 6
    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 Mar 29 '17 at 16:10
  • @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 Mar 29 '17 at 16:16
  • 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 Mar 29 '17 at 16:16
  • 2
    A list comprehension desugars to monadic code (using the `guard` function), not a composition of `filter` and `map`. – chepner Mar 29 '17 at 16:29
  • What do you think should `filter (<20) ([1..]++[1])` yield, it is not too much different from your original example – epsilonhalbe Mar 29 '17 at 17:56
  • 1
    @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 Mar 30 '17 at 08:52

2 Answers2

3

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.

9000
  • 39,899
  • 9
  • 66
  • 104
  • so this basically means list-comprehensions can really screw you over... thanks a lot for the quick answer. I don't have a specific problem I am trying to optimize but as I am new to Haskell I try to get a better understanding of what the compiler will do for you and what not. – Chris Mar 29 '17 at 16:32
  • 2
    @Chris: it's not comprehensions, it's infinite sequences that need handling with care; infinite loops in any other language need an extra bit of attention, too. – 9000 Mar 29 '17 at 17:00
3
[<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.

Pedro Castilho
  • 10,174
  • 2
  • 28
  • 39