[erlang-questions] List comprehension questions

38 views
Skip to first unread message

Olivier BOUDEVILLE

unread,
Mar 30, 2011, 7:29:53 AM3/30/11
to erlang-q...@erlang.org

Hi,

Reading http://www.erlang.org/doc/reference_manual/expressions.html#id77052 it is not obvious that the order induced by a single generator is necessarily preserved by the comprehension, as nevertheless suggested by all experiments like:

1> [ X || X <- [1,2,3] ].
[1,2,3]

I suppose this order preservation is true. Then, I imagine that, internally, list comprehensions are translated to code very similar to the one that would be produced if the developer had written an appropriate accumulator-based tail-recursive function?

If so, does it imply that using a list comprehension on a semantically unordered set of elements will involve a useless reversal (like lists:reverse/1) of the resulting list?

Thanks in advance for any answer,
Best regards,

Olivier Boudeville.
---------------------------
Olivier Boudeville

EDF R&D : 1, avenue du Général de Gaulle, 92140 Clamart, France
Département SINETICS, groupe ASICS (I2A), bureau B-226
Office : +33 1 47 65 59 58 / Mobile : +33 6 16 83 37 22 / Fax : +33 1 47 65 27 13



Ce message et toutes les pièces jointes (ci-après le 'Message') sont établis à l'intention exclusive des destinataires et les informations qui y figurent sont strictement confidentielles. Toute utilisation de ce Message non conforme à sa destination, toute diffusion ou toute publication totale ou partielle, est interdite sauf autorisation expresse.

Si vous n'êtes pas le destinataire de ce Message, il vous est interdit de le copier, de le faire suivre, de le divulguer ou d'en utiliser tout ou partie. Si vous avez reçu ce Message par erreur, merci de le supprimer de votre système, ainsi que toutes ses copies, et de n'en garder aucune trace sur quelque support que ce soit. Nous vous remercions également d'en avertir immédiatement l'expéditeur par retour du message.

Il est impossible de garantir que les communications par messagerie électronique arrivent en temps utile, sont sécurisées ou dénuées de toute erreur ou virus.
____________________________________________________

This message and any attachments (the 'Message') are intended solely for the addressees. The information contained in this Message is confidential. Any use of information contained in this Message not in accord with its purpose, any dissemination or disclosure, either whole or partial, is prohibited except formal approval.

If you are not the addressee, you may not copy, forward, disclose or use any part of it. If you have received this message in error, please delete it and all copies from your system and notify the sender immediately by return message.

E-mail communication cannot be guaranteed to be timely secure, error or virus-free.

Robert Virding

unread,
Mar 31, 2011, 1:40:09 PM3/31/11
to Olivier BOUDEVILLE, erlang-q...@erlang.org
List comprehensions work as a combined lists:map and lists:filter. So you map over a list filtering out elements you don't want in the output list. They have the added functionality that they can handle this for nested lists.

The expanded code is in fact quite simple and is close to what you probably write yourself.

So order is preserved and their is no call to lists:reverse when generating the output list.

Robert

> _______________________________________________ erlang-questions mailing list erlang-q...@erlang.org http://erlang.org/mailman/listinfo/erlang-questions

Olivier BOUDEVILLE

unread,
Apr 1, 2011, 4:00:30 AM4/1/11
to robert....@erlang-solutions.com, erlang-q...@erlang.org

Hello Robert,

Thanks for your explanation. I guess that the reversal (to restore the original list order after a first "if selected by filter then apply" traversal) is done then in the list:map/2 counterpart!

My concern was that, for long lists which do not happen to have to respect any particular order in their elements, two traversals would be done with list comprehensions whereas just one could be sufficient. Well, a minor concern as for such cases we can write our own functions to do so in one pass.


Thanks again,
Best regards,

Olivier Boudeville.
---------------------------
Olivier Boudeville

EDF R&D : 1, avenue du Général de Gaulle, 92140 Clamart, France
Département SINETICS, groupe ASICS (I2A), bureau B-226
Office : +33 1 47 65 59 58 / Mobile : +33 6 16 83 37 22 / Fax : +33 1 47 65 27 13



robert....@erlang-solutions.com

31/03/2011 19:40

A
olivier.b...@edf.fr
cc
erlang-q...@erlang.org
Objet
Re: [erlang-questions] List comprehension questions


Olivier BOUDEVILLE

unread,
Apr 1, 2011, 7:15:14 AM4/1/11
to carlsson...@gmail.com, erlang-q...@erlang.org

Hello Richard,

First of all, sorry, I had indeed missed your answer. Actually I did not see it neither at work nor at home, and I wonder whether there is not a mailing-list problem as it does not seem to appear either in gmane or in the thread as shown (at least at the time of this writing) by google groups (http://groups.google.com/group/erlang-programming/browse_thread/thread/8d339e24ed090311).

Back on topic: as I understand now (I am not too familiar with Core Erlang), list comprehensions generate local functions that are body-recursive, i.e. involve actually a direct recursion, not using an accumulator.

I just happened to find http://www.erlang.org/doc/efficiency_guide/listHandling.html#id61285 which gives a similar explanation (maybe a link from the reference manual to the efficiency guide could be made, to associate these two list comprehension topics).

I was wondering if this body-recursiveness did not imply that a list comprehension operating on a longer list, whose result would be kept, could eat a lot of stack space/take longer to execute than a tail-recursive version?

Apparently according to http://www.erlang.org/doc/efficiency_guide/myths.html#id58884 this will probably not be the case, so using list comprehension does not involve much trade-off.

Thanks again,
Best regards,

Olivier Boudeville.
---------------------------
Olivier Boudeville

EDF R&D : 1, avenue du Général de Gaulle, 92140 Clamart, France
Département SINETICS, groupe ASICS (I2A), bureau B-226
Office : +33 1 47 65 59 58 / Mobile : +33 6 16 83 37 22 / Fax : +33 1 47 65 27 13



carlsson...@gmail.com

01/04/2011 10:46

A
erlang-q...@erlang.org, olivier.b...@edf.fr
cc
Objet
Re: [erlang-questions] Re: List comprehension questions





On 04/01/2011 10:00 AM, Olivier BOUDEVILLE wrote:
>
> Hello Robert,
>
> Thanks for your explanation. I guess that the reversal (to restore the
> original list order after a first "if selected by filter then apply"
> traversal) is done then in the list:map/2 counterpart!
>
> My concern was that, for long lists which do not happen to have to
> respect any particular order in their elements, two traversals would be
> done with list comprehensions whereas just one could be sufficient.
> Well, a minor concern as for such cases we can write our own functions
> to do so in one pass.

Perhaps you didn't see my reply to your original mail (repeated below).
The point that both Robert and I are trying to make is that there is no
reversal involved in the code, and it only does one traversal, so you
don't need to worry about this.

    /Richard



On 03/30/2011 01:29 PM, Olivier BOUDEVILLE wrote:
> Reading
> http://www.erlang.org/doc/reference_manual/expressions.html#id77052 it
> is not obvious that the order induced by a single generator is
> necessarily preserved by the comprehension, as nevertheless suggested by
> all experiments like:
>
> 1> [ X || X <- [1,2,3] ].
> [1,2,3]
>
> I suppose this order preservation is true. Then, I imagine that,
> internally, list comprehensions are translated to code very similar to
> the one that would be produced if the developer had written an
> appropriate accumulator-based tail-recursive function?
>
> If so, does it imply that using a list comprehension on a semantically
> unordered set of elements will involve a useless reversal (like
> lists:reverse/1) of the resulting list?

No, the translation does a straightforward recursion over the list
without accumulator, automatically preserving order. To see what
happens, take for example the following module:

  -module(lc).
  -export([f/1]).
  f(Input) ->
    [N + 1 || N <- Input].

and compile it to Core Erlang with c(lc,[to_core]) or erlc +to_core
lc.erl. The resulting file lc.core contains the following code:

  'f'/1 =
    fun (_cor0) ->
        letrec
            'lc$^0'/1 =
                fun (_cor3) ->
                    case _cor3 of
                      <[N|_cor2]> when 'true' ->
                          let <_cor4> =
                              call 'erlang':'+'
                                  (N, 1)
                          in  let <_cor5> =
                                  apply 'lc$^0'/1
                                      (_cor2)
                              in  ( [_cor4|_cor5]
                                    -| ['compiler_generated'] )
                      <[]> when 'true' ->
                          []
                      ( <_cor3> when 'true' ->
                            primop 'match_fail'
                                ({( 'function_clause'
                                    -| [{'name',{'lc$^0',1}}] ),_cor3})
                        -| ['compiler_generated'] )
                    end
        in  apply 'lc$^0'/1
                (_cor0)

(The annotations ( Expr -| 'compiler_generated') on some subexpressions
are mostly needed to suppress certain compilation warnings that might
otherwise be triggered, such as for unused results of expressions.)

    /Richard

James Churchman

unread,
Apr 1, 2011, 1:24:22 PM4/1/11
to Olivier BOUDEVILLE, carlsson...@gmail.com, erlang-q...@erlang.org
So if (from the docs) list comprehension become : 
'lc^0'([E|Tail], Expr) -> [Expr(E)|'lc^0'(Tail, Expr)];
'lc^0'([], _Expr) -> [].
then, what happens when Expr contains references to other variables in the original scope? (eg not E ) it says  Expr used to be a Fun, but now it's not, so in this case is it a Fun, or does it increase the arty of the generated lc^0 function for each of the extra referenced vars?

Also keen to know the body recursive "cost", and why it avoids using list reverse in the case when a list is required to be returned :-)

james



E-mail communication cannot be guaranteed to be timely secure, error or virus-free._______________________________________________

James Churchman

unread,
Apr 2, 2011, 7:25:39 AM4/2/11
to Richard Carlsson, erlang-q...@erlang.org
Hi Richard

Thanks for your reply. The following part of the docs actually shows that it does do the non-return optimisation:-) tho you answer also make me question all my carefully crafted non-body recursive functions with reverses too !


James


On 1 Apr 2011, at 20:08, Richard Carlsson wrote:

> On 2011-04-01 19:24, James Churchman wrote:
>> So if (from the docs) list comprehension become :
>>
>> 'lc^0'([E|Tail], Expr) -> [Expr(E)|'lc^0'(Tail, Expr)];
>> 'lc^0'([], _Expr) -> [].
>>
>> then, what happens when Expr contains references to other variables in
>> the original scope? (eg not E ) it says Expr used to be a Fun, but now
>> it's not, so in this case is it a Fun, or does it increase the arty of
>> the generated lc^0 function for each of the extra referenced vars?
>

> Essentially, yes, it increases the arity. First, the list comprehension becomes a local function in Core Erlang (with access to the variables in scope). The local function is then lifted out to become a normal function with additional parameters before it gets translated to BEAM.


>
>> Also keen to know the body recursive "cost", and why it avoids using
>> list reverse in the case when a list is required to be returned :-)
>

> A body recursive translation is simpler, and is generally faster for short lists (the majority of list comprehensions runs on lists shorter than 100 elements, in my experience at least, and the break-even point for tail recursion plus reverse is somewhere above 100 elements).
>
> Even for quite long lists, a body recursive function is typically not much worse than a tail recursive solution with a reverse at the end, so there's no reason to change the behaviour and make it worse for short lists. Hence, the current implementation never produces a list in reverse order, and it never needs to reverse anything at the end.
>
> If the compiler knows that the result (which is always a list) won't be used at all, it could generate code more similar to lists:foreach() instead, but I don't think that's done currently.
>
> /Richard

Björn Gustavsson

unread,
Apr 3, 2011, 2:30:06 AM4/3/11
to James Churchman, Richard Carlsson, erlang-q...@erlang.org
> On 1 Apr 2011, at 20:08, Richard Carlsson wrote:
>
>> On 2011-04-01 19:24, James Churchman wrote:
[...]

>>> Also keen to know the body recursive "cost", and why it avoids using
>>> list reverse in the case when a list is required to be returned :-)
>>
>> A body recursive translation is simpler, and is generally faster for short lists (the majority of list comprehensions runs on lists shorter than 100 elements, in my experience at least, and the break-even point for tail recursion plus reverse is somewhere above 100 elements).
>>
>> Even for quite long lists, a body recursive function is typically not much worse than a tail recursive solution with a reverse at the end, so there's no reason to change the behaviour and make it worse for short lists. Hence, the current implementation never produces a list in reverse order, and it never needs to reverse anything at the end.

There used to be a more noticeable difference between
body recursion and tail recursion before the R12B release,
because body recursion would usually use more memory.
In R12B and later releases, the tail-recursive and
body-recursive variants of a function generally use the
same amount of memory and executes roughly in the
same time. See:

http://www.erlang.org/doc/efficiency_guide/myths.html#id58884

>> If the compiler knows that the result (which is always a list) won't be used at all, it could generate code more similar to lists:foreach() instead, but I don't think that's done currently.

It's done. See:

http://www.erlang.org/doc/efficiency_guide/listHandling.html#id61285

--
Björn Gustavsson, Erlang/OTP, Ericsson AB

Reply all
Reply to author
Forward
0 new messages