list comprehension question

[Richard A. O'Keefe]

Charles Blair <chas@REDACTED> 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.