optimization of list comprehensions

Richard A. O'Keefe <>
Thu Mar 9 02:06:01 CET 2006


Mats Cronqvist <> wrote:
	   i see you didn't bother clicking on that link.
	
It's not a matter of "didn't bother", it's a matter of CAN'T.
Because I keep sensitive assignment and examination details on my machine,
I need to use a secure Mail User Agent.
The one I use *doesn't* have a GUI and *can't* follow links (so it can't
follow links of malware either).
To follow that link I'd have to switch over to another machine and type
the link in by hand.

Sprenger and Kramer (the authors of Malleus Malleficarum) got a lot of
things wrong, but they got one thing right:  when you quote, qoute enough
so that your reader doesn't *have* to look up the volume.

OK, so _that_ message used round parentheses for folding,
but _other_ messages in this thread have used round parentheses
for so-the-side-effects-and-throw-the-results-away.

Let's look at the syntax again:

    (expr(X1,...,Xn,Y1,...,Ym) || PatX <- List, PatY <-- Acc0
=>
    lists:foldl(fun(PatX, PatY) -> expr(X1,...,Xn,Y1,...,Ym) end,
                List, Acc0)

So the whole difference between

    (f(X,Y) || X <- List, Y <- Init)
				% _ = [f(X,Y) || X <- List, Y <- Init]
and
    (f(X,Y) || X <- List, Y <-- Init
				% foldl(fun(X,Y)->f(X,Y) end, List, Init)

is that one of them has Y <- Init (one dash) and the other has
Y <-- Init (two dashes).  NOT a good notation.  Also, not a completely
defined notation.  List comprehensions allow multiple generators, and
also filters.
    - can you put Y <-- before X <- ?
    - why is the order of X <- and Y <-- the *opposite* of the order
      you would expect from list notation?
    - does this notation allow multiple generators?
    - does it allow multiple <-- accumulators?
    - does it allow filters?
(In that message, the answer is
    - don't know, not stated
    - don't know, author didn't apparently realise it made a difference
    - no, author said not clear how to do this
    - no, a major weakness (you have to use tuples, which misses the point)
    - no, thought to be "trivial" but not actually done

(You'll perceive from this that I _have_ fired up the other machine and
_have_ retyped that URL.  What a waste of my time.)

We don't need incomplete "solutions".

Turn the syntax inside out:

    ( Result_Expr
      where ( Pat1 = Init1 then Step1, ..., Patn = Initn then Stepn
      || generators and filters
    )

so the sum-a-list-of-pairs example from the cited message isn't
the confusing
    ({X+XAcc,Y+YAcc} || {X,Y} <- List, {XAcc,YAcc} <-- {0,0})
but
    ({XSum,YSum}
     where XSum = 0 then XSum+X, YSum = 0 then YSum+Y || {X,Y} <- List
    )
where the existence of multiple accumulators means that even a fairly
dumb compiler could avoid generating the intermediate tuples.

Pat = Init then Pat could be written as Pat = Init, thus introducing
a local binding, and if there are no Step expressions, there needn't
be a || part either, so

    ({X,Y} where X = ..., Y = ...)

would be the Erlang equivalent of a Haskell 'where', something that
some Erlang programmers have wanted for years.

	   the example was just that; an example, and kept deliberately simple at that.

That simply won't _do_ as an argument.
It was supposed to be a good enough example to make the point.
In fact it supports the opposite point.
So far, we don't have *any* realistic examples where a new notation
would help.

	   the point of the example was that fold-like comprehensions
	would change the way people write code.

But that example did NOT demonstrate that point.

What we need is *realistic* examples.
Ideally, examples taken from actual working code.

	alas, i am not a researcher (any longer).  but maybe i can find
	the time to grep around a bit in the sources.
	
You don't have to be a "researcher" to publish..

	> But if I understand you, you are claiming that normal industry programmers
	> are incompetent, ineducable, or both.
	
	   no, you do most certainly not understand me.  and it actually
	seems you're making a concious effort to misunderstand.
	
I may not have understood *you*, but I certainly understood what you
wrote.  You made the (arguably defamatory) claim that "normal industry
programmers" were unable or unwilling to use a fundamental aspect of
the language appropriately.

	   i don't think a reluctance to use funs indicates incompetence.

If we were talking about C++ or Java, you could be right.
But in a functional language?  This is like claiming that a reluctance
to use classes is compatible with competence in C++.

	   i remain convinced that fold-like comprehensions would be an
	excellent thing, just like map-like comprehensions were.

That's nice for you.  How about trying to convince others?

What we need are realistic (ideally _real_) examples of code which can
be made a lot more readable by some good notation.

The notation I've used in this message is beginning to seem plausible.
I'm particularly pleased that it has a the ISWIM 'where' as a natural
special case.

But the fact that I've now found a notation for this job that I like
does not mean that I think there is evidence that Erlang would be the
better for including it.  For that, we need evidence.




More information about the erlang-questions mailing list