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:
>>
>>> I have been thinking about this a bit and I wonder if the 
>>> 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
>>>>
>>>
>>




More information about the erlang-questions mailing list