[Haskell-cafe] list comprehansion performance has hug different

Richard O'Keefe ok at cs.otago.ac.nz
Wed Jan 30 01:20:10 CET 2013

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'
Generating Y before X yields
 'h called'
 'g called'
 'g called'

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).

More information about the Haskell-Cafe mailing list