optimization of list comprehensions

Richard A. O'Keefe ok@REDACTED
Mon Mar 6 02:35:46 CET 2006


I wrote:
	> I am not at all happy about (Expr || Pat <- List) because
	> (A) it looks like a syntax error; it's quite likely to be 'corrected'
	>     to use square brackets

Mats Cronqvist <mats.cronqvist@REDACTED> replied:
	   "looks like a syntax error"?  doesn't that depend on what the
	syntax is?

No.  It depends on what people *THINK* it is.  The term was "looks like",
not "is".

	"corrected" by whom?

People, what else?  Maintenance programmers often fix things that aren't
really broken (sometimes until it _is_ broken; the KMP pattern matcher
is a good example.)  They are especially likely to fix things that LOOK
broken.

	anyway, the use of '(' and ')' is incidental, the point is 
	to not use '[' and ']' (to make it clear that we're not
	returning a list).
	
But with everything else so very strongly resembling the syntax for
a list comprehension, the use of round parentheses is NOT enough to
make it CLEAR that we are not returning a list.

If you really want to be clear, make it

    (do Expr for Pat <- List)

with the trivial case of iterating over no lists being

    (do Expr)

	   surely using the [] notation is even worse in that regard.
	
A headache may not be as bad as a toothache; but if I have a toothache
it doesn't help me much to give me a headache as well.

	> As for combining accumulation with list comprehension,
	> one can already write
	>     lists:foldl(fun (X,Y) -> X+Y end, 0, 
	> 	        [some list comprehension goes here])
	> which isn't *that* bad.  
	
	   i think it is that bad :>

	   here's the thing.  the list comprehensions were introduced
	for no good reason, in that they added nothing that you could
	not already do.  but they make my life easier because they offer
	a much more succinct notation (especially since i have to look
	at other people's code a lot).

I think you just said that making your life easier is not a good reason.

One really important thing here is that there was *precedent* for
list comprehensions.  By the time Erlang got them, list comprehension
was a well established notation (up to choice of punctuation marks)
which had proven itself in several different languages.  (Even Prolog
all-solutions" operations are related, and, by the way, always construct
lists.)

If you except Interlisp and Common Lisp, there *isn't* any precedent
for a comprhenion-cum-fold.  So the risk of doing it badly is high;
it's not just a matter of adopting an already-existing notation.  And
the evidence so far bears this out:  the actual concrete proposals in
this thread are quite astonishingly BAD.

i want the same improvement for
	fold-like list operations.
	
	> Any more direct syntax (such as something
	> based on the Lisp 'do' construct, for example) would have to involve
	> some way of presenting two bindings for the same names in the same
	> construct (as 'do' does), which is not a very Erlangish thing to do.
	
	   being an old FORTRAN programmer i had no idea what the Lisp 'do' construct 
	was. it is indeed (as far as i can tell) exactly what i want. thanks for the 
	educational reference.
	
Here's the translation:

    (DO ((var-1 init-1 step-1)
         ...
         (var-n init-n step-n))
        (end-test result-expr)
       (stmt-1)
       ...
       (stmt-k))

=
    (LETREC ((dummy (LAMBDA (var-1 ... var-n)
                      (IF end-test
                          result-expr
                          (BEGIN
                            (stmt-1)
                            ...
                            (stmt-k)
                            (dummy step-1 ... step-n))))))
      (dummy init-1 ... init-n))

In words:
    Bind variables var-1 to var-n to the values of the initial
    expressions init-1 to init-n.
    While the end-test is not true,
       perform the statements in the body (a "pure" use of DO
       has no statements)
       evaluate the step expressions step-1 to step-n
       and rebind var-1 to var-n to their values
    Finally return the value of result-expr.

There is no actual mutation here, just rebinding.  The translation makes
that explicit by constructing a recursive function with the iteration being
tail recursion.

Just scribbling down syntax ad hoc, one might do something like this
in Erlang as

    let Pattern1 = Expr1 [then Expr2 for Pattern2 <- Expr3]
    in Expr4

So we might do

    let X = 0 then X+Y for {'fred',Y} <- Some_List in X

with the translation being something like

    (fun(Pattern1) -> Expr4 end)(lists:foldl(
     fun(Pattern1,Pattern2) -> Expr2 end, Expr1,
	[Pattern2 || Pattern2 <- Expr3]))




More information about the erlang-questions mailing list