# list comprehension question

Richard A. O'Keefe < >
Fri Jul 29 03:57:41 CEST 2005

```Charles Blair < > worried that:
Thompson, in Haskell: The Craft of Functional Programming, describes
the program for computing permutations by means of list comprehensions
in part as "If xs is not empty, a permutation is given by picking an
element x from xs and putting x at the front of the permutation of the
remainder ..."--he does not say "by picking the first element", and
this algorithm corresponds exactly to the one given in Programming
Examples 3.3, and since the documentation for lists:map says "The
evaluation order is implementation dependent" (and it is lists:map
which is implicated in 3.5),

Reassurance:
(1) List comprehension is defined in the Haskell report by source-to-source
transformation to normal function calls.  Here are the rules:

[e | True]		-> [e]
[e | x]			-> [e | x, True]
[e | test, &c]		-> if test then [e | &c] else []
[e | pat <- exp, &c]	-> concatMap (\pat -> [e | &c]
_   -> []) exp
[e | let decls, &c]	-> (let decls in [e | &c])

where
concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f [] = []
concatMap f (x:xs) = f x ++ concatMap f xs

We can figure out from this that a simple
[ expr | pat <- list, guard ]
is equivalent to
let f (pat : xs) | guard = expr : f xs
f ( _  : xs)         = f xs
f []                 = []
in f list
This simplified case and the general case both MUST preserve the order
of elements, according to the Haskell specification.

(2) I think the comment about lists:map/2 has been misunderstood.
map(F, [X1,...,Xn])
is equivalent to
[F(X1), ..., F(Xn)]
When the comment says that the *evaluation* order is undefined,
it means that there is no promise about whether F(X1) or F(Xn)
will be *evaluated* first.  There *is* a promise about which of
them will be (spatially) first in the result.

To make this clearer, imagine the following two definitions of map:

map2(F, [X|Xs]) ->		map1(F, [X|Xs]) ->
T = map2(F, Xs),		    H = F(X),
H = F(X),			    T = map1(F, Xs),
[H|T];			    [H|T];
map2(_, []) ->			map1(_, []) ->
[].				    [].

If F is free of side effects, map1/2 and map2/2 will always give the
same order:  the order of elements within the result is defined.  But
they *evaluate* those elements in opposite orders.

```

More information about the erlang-questions mailing list