[Haskell-cafe] list comprehansion performance has hug different

[Richard O'Keefe]

On 29/01/2013, at 10:59 PM, Junior White wrote:

> So this is a problem in lazy evaluation language, it will not appear in python or erlang, am i right?

Wrong.  Let's take Erlang:

	[f(X, Y) || X <- g(), Y <- h()]

Does the order of the generators matter here?
You _bet_ it does.
First off, in all of these languages, it affects
the order of the results.  Let's take a toy case:

	g() -> [1,2].
	h() -> [a,b].     % constants
	f(X, Y) -> {X,Y}. % a pair

[f(X, Y) || X <- g(), Y <- h()]
 yields [{1,a},{1,b},{2,a},{2,b}]
[f(X, Y) || Y <- h(), X <- g()]
 yields [{1,a},{2,a},{1,b},{2,b}]

Now let's change it by giving g/0 and h/0 (benign) side effects.
 g() -> io:write('g called'), io:nl(), [1,2].
 h() -> io:write('h called'), io:nl(), [a,b].
Generating X before Y yields
 'g called'
 'h called'
 'h called'
 [{1,a},{1,b},{2,a},{2,b}]
Generating Y before X yields
 'h called'
 'g called'
 'g called'
 [{1,a},{2,a},{1,b},{2,b}]

If a function call may yield side effects, then the compiler
must not re-order or coalesce calls to that function.
This applies to both Erlang and Python (and to SETL, which
had set and tuple comprehensions before Erlang, Python, or
Haskell were conceived).