Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why do Haskell list comprehensions with multiple generators treat the rightmost generator as the tightest loop?

I'm reading through the Gentle Introduction and am wondering why in a list comprehension with two generators, the rightmost generator is iterated "the fastest" (i.e. compiles to the innermost loop, I guess). Observe the following GHCi output:

*Main> concat [[(x,y) | x <- [0..2]] | y <- [0..2]]
[(0,0),(1,0),(2,0),(0,1),(1,1),(2,1),(0,2),(1,2),(2,2)]
*Main> [(x,y) | x <- [0..2], y <- [0..2]]
[(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)]

If the leftmost generator were iterated fastest, the above two expressions would have the same value, which I think makes choosing this convention more natural somehow.

So does anyone know why the opposite convention was chosen? I notice Python has the same convention as Haskell (maybe even borrowed it from Haskell?), and in Python world the word seems to be that the ordering was chosen "because that's the order in which you'd write a for loop", but I gather that thinking in terms of for loops is not exactly what most Haskell programmers do...

Thoughts?


From my comment on Louis Wasserman's answer below:

I guess here the order corresponding to an imperative-style explication of the comprehension was considered more natural than having it correspond with nesting the list. So in essence the Haskell explanation for this is the same as the Python explanation I linked in the question, after all, it seems.

like image 935
kini Avatar asked May 01 '12 15:05

kini


People also ask

How list comprehension works in Haskell?

List comprehension in Haskell is a way to produce the list of new elements from the generator we have passed inside it. Also for the generator values, we can apply the Haskell functions to modify it later. This list comprehension is very y easy to use and handle for developers and beginners as well.

Does Haskell support list comprehension?

The specification of list comprehensions is given in The Haskell 98 Report: 3.11 List Comprehensions. The GHC compiler supports parallel list comprehensions as an extension; see GHC 8.10. 1 User's Guide 9.3. 13.


1 Answers

So that things scope in a sane way.

[(x, y) | x <- [1..10], y <- [1..x]]

makes sense -- x is in scope for the comprehension on y -- but

[(x, y) | y <- [1..x], x <- [1..10]]

makes somewhat less sense.

Additionally, this way it's consistent with the do monad syntax:

do x <- [1..10]
   y <- [1..x]
   return (x, y)
like image 127
Louis Wasserman Avatar answered Oct 18 '22 18:10

Louis Wasserman