How are list comprehensions implemented in Haskell?

Question

Are list comprehensions simply a language feature?
What's the easiest way to fake a list comprehension using pure Haskell?
Do you have to use a do block/>>= to do this or could you use some other method for hacking a list comprehension together?

Clarification: By "fake" a list comprehension I mean create a function that takes the same input and produces the same input, i.e. a form for the return values, lists to crunch together, and a predicate or multiple predicates.

[This](http://www.haskell.org/haskellwiki/List_comprehension) may answer some of your questions. It explains how comprehensions are syntactic sugar for do notation, which themselves are just syntactic sugar for `>>=`, but I really don't know what you mean by "fake a list comprehension using pure Haskell". It _is_ pure Haskell, according to the Haskell specification. — bheklilr, Dec 19 '13 at 17:26
I added a clarification, but I really don't understand why this is getting so many down votes, I'm just asking how a list comprehension could be written without using a list comprehension to better understand them. — reem, Dec 19 '13 at 17:33

score 21 · Accepted Answer · edited Jan 16 '14 at 01:04

21

Section 3.11 in the Haskell report describes exactly what list comprehensions mean, and how to translate them away.

If you want monad comprehensions you basically need to replace [e] by return e, [] by mzero, and concatMap by (>>=) in the translation.

edited Jan 16 '14 at 01:04

Pang

9,564
146
81
122

answered Dec 19 '13 at 17:36

augustss

22,884
5
56
93

score 13 · Answer 2 · answered Dec 19 '13 at 19:23

To augment augustss's answer, if you have something like:

[(x, y) | x <- [1..3], y <- [1..3], x + y == 4]

... it is equivalent to this use of do notation:

do x <- [1..3]
   y <- [1..3]
   guard (x + y == 4)
   return (x, y)

... which is equivalent to this use of concatMap:

concatMap (\x ->
    concatMap (\y ->
        if (x + y == 4) then [(x, y)] else []
        ) [1..3]
    ) [1..3]

How are list comprehensions implemented in Haskell?

2 Answers2

Linked