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