# optimization of list comprehensions

Per Gustafsson <>
Thu Mar 2 16:27:57 CET 2006

```Hi Mats

Do I understand your construction correctly if I describe it like this:

A fold-expression have the following syntax:

(expr(X1,..XN,Y1,...,YM) || PatX <- List, PatY <-- Acc0)

Where X1,...,XN are variables from PatX and Y1,...,YN are variables from
PatY, List is the list to fold over and Acc0 is the initial accumulator.

This can be translated into the following code using lists:foldl:

lists:foldl(fun(PatX,PatY) -> expr(X1,...,XN,Y1,...,YM) end,
List, Acc0)

An example to calculate the sum of a list of two-tuples:

two_tuple_sum(List) ->
({X+XAcc,Y+YAcc} || {X,Y} <- List, {XAcc,YAcc} <-- {0,0})

It is trivial to add filters to this construction as well. It is less
clear to me how it would work with multiple generators.

To get mapfoldl would be a little bit trickier (less natural) but the
following syntax could do the trick:

[expr(X1,..XN,Y1,...,YM) || PatX <- List, PatY <-- Acc0]

where expr(X1,..XN,Y1,...,YM) returns a two-tuple and the whole
expression returns a two-tuple. (Which is unfortunate as it seems to
return a list)

This can be translated into the following code using lists:mapfoldl:

lists:mapfoldl(fun(PatX,PatY) -> expr(X1,...,XN,Y1,...,YM) end,
List, Acc0)

An example to calculate the sum of a list and decrease each value in the
list by one:

sum_and_dec(List) ->
[{X-1,X+Acc} || X<-List Acc <-- 0]

Of course to get the foldr, mapfoldr versions the list generator should
be written: List -> PatX  :)

I feel that the issue with adding (too many) of these kinds of
constructs are that they tend to make the language harder to read
because it becomes difficult to see the difference between the different
constructs that look quite similar. Another issue is that it probably
would be quite difficult to convince the parser to accept this.

Per Gustafsson

Mats Cronqvist wrote:
>   indeed. i tend to use lists:foldl, lists:map and lists:foreach a lot.
> i would really like to have comprehension syntax for all three of them.
>
>   my suggestion for the foldl-like comprehension is
>
> (x(I,'_') || I <- List, '_' <- Acc0) -> Acc1
>
>   where '_' is the accumulator. it would shadow a previously bound '_'.
> the foreach comprehension
>
> (x(I) || I <- List) -> X
>
>   (where X is x(L) and L is the last element of List) would be a special
> case of this.
>
>    all real language designers should feel free to flame me. it'll be
> educational.
>
>   mats
>
> Serge Aleynikov wrote:
>
>> I do want to throw a vote for Mats' suggestion on the alternative syntax:
>>
>> (I || I <- List) -> ok
>>
>> What I also find limiting is that it's not possible to have an
>> accumulator when using list comprehension.  Perhaps something like
>> this could also be considered (unless someone can suggest a better
>> syntax):
>>
>> [Acc+1, I || Acc, I <- List](0) -> Acc1
>>                              ^
>>                              |
>>                        Initial Acc's value
>> Serge
>>
>> Robert Virding wrote:
>>
>>> constructing of the return list really causes any problems.
>>> Space-wise it will only be as large as the size of the input list, so
>>> I wouldn't worry.
>>>
>>> Robert
>>>
>>> Ulf Wiger (AL/EAB) skrev:
>>>
>>>> I've seen many examples of how people use
>>>> list comprehensions as a form of beautified
>>>> lists:foreach() - that is, they don't care
>>>> about the return value of the comprehension.
>>>>
>>>> I hesitate to say that it's bad practice,
>>>> even though one will build a potentially
>>>> large list unnecessarily, since it's actually looks a lot nicer than
>>>> using lists:foreach().
>>>>
>>>> Question: would it be in some way hideous
>>>> to introduce an optimization where such
>>>> list comprehensions do everything except
>>>> actually build the list? Then they could
>>>> execute in constant space.
>>>>
>>>> /Ulf W
>>>>
>>>
>>

```