[erlang-questions] [erlang-question] How to comprehend two lists synchronously?

Ladislav Lenart <>
Fri Nov 18 11:09:49 CET 2011


Please read this:

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

Myth 2.3, especially the fifth paragraph, talks exactly about this
(the emphasis is mine):

     In R12B and later releases, there is an optimization that will in many
     cases reduces the number of words used on the stack in body-recursive
     calls, so that a body-recursive list function and tail-recursive function
     that calls lists:reverse/1 at the end will use *exactly the same amount of
     memory*. lists:map/2, lists:filter/2, list comprehensions, and many other
     recursive functions now use the same amount of space as their tail-recursive
     equivalents.

My understanding of this is that if your recursive function produces result
proportional in size to the input (e.g. lists:map/2), use body-recursive call
(which is easier to read and understand) and let the compiler do its job.


HTH,

Ladislav Lenart


On 18.11.2011 09:36, Barco You wrote:
> Umm! I don't think there would be some difference between times consumed by these two functions, but I will assume there are difference in memory consumption.
>
>
>
> On Fri, Nov 18, 2011 at 3:49 PM, Dmitry Demeshchuk < <mailto:>> wrote:
>
>     I think it's meant that lists:reverse/1 is called at the end of the
>     _optimized_ code.
>
>     Here's the module code:
>
>     -module(test).
>     -export([a/0, b/0]).
>
>     a() ->
>         L = lists:seq(1, 10000000),    map2(fun (I, J) -> I + J end, L, L).
>
>     b() ->
>         L = lists:seq(1, 10000000),
>         map3(fun (I, J) -> I + J end, L, L).
>
>
>     map2(Fun, [H1 | T1], [H2 | T2]) ->
>         [Fun(H1, H2) | map2(Fun, T1, T2)];
>     map2(_, [], []) ->
>         [].
>
>     map3(_Fun, [], []) ->
>        [];
>     map3(Fun, L1, L2) ->
>        map3(Fun, L1, L2, []).
>
>     map3(_Fun, [], [], L) ->
>        lists:reverse(L);
>     map3(Fun, [H1 | T1], [H2 | T2], L) ->
>        map3(Fun, T1, T2, [Fun(H1, H2) | L])
>
>     Try to call timer:tc/3 yourself.
>
>     On Fri, Nov 18, 2011 at 11:48 AM, Barco You < <mailto:>> wrote:
>      > According to the instruction attached by Ulf, the body-recursive and
>      > tail-recursive list function will be the same in consuming memory only when
>      > they call lists:reverse/1 at the end.
>      > So, I don't know how did you do the benchmarks. Did you compare these two
>      > methods with big enough lists?
>      > Or, I misunderstand the optimization instructions?
>      >
>      > BR,
>      > Barco
>      >
>      > On Fri, Nov 18, 2011 at 3:37 PM, Dmitry Demeshchuk < <mailto:>>
>      > wrote:
>      >>
>      >> Okay, I admit, this isn't an "honest" tail-recursed function, since a
>      >> list concatenation operator is going to be called at the end. However,
>      >> Erlang compiler optimizes such cases and converts them to
>      >> tail-recursive:
>      >> http://www.erlang.org/doc/efficiency_guide/myths.html#tail_recursive
>      >>
>      >> Also, I've ran benchmarks with both implementations: mine and yours.
>      >> And they result in the same performance.
>      >>
>      >> On Fri, Nov 18, 2011 at 11:06 AM, Barco You < <mailto:>> wrote:
>      >> > Yes, Ryan's suggestion is a good generic solution for n lists and it's
>      >> > tail-recursed.
>      >> > Hi Dmitry,
>      >> > Your version is just recursed but not tail-recursed, because your
>      >> > function
>      >> > needs a piece of memory to stack the intermediate result for every round
>      >> > of
>      >> > recursive calls. To be tail-recursed, the recursive calls should
>      >> > eliminate
>      >> > the linearly-increased memory consumption by adding an extra variable
>      >> > (accumulator) and let the recursive function call it alone for every
>      >> > round.
>      >> >
>      >> > On Fri, Nov 18, 2011 at 2:53 PM, Dmitry Demeshchuk
>      >> > < <mailto:>>
>      >> > wrote:
>      >> >>
>      >> >> Hi, Barco.
>      >> >>
>      >> >> Why do you think my version isn't tail-recursed? :) Take a look at
>      >> >> lists:map/2 implementation, for example. It's just the same.
>      >> >>
>      >> >> List comprehensions just serve different purpose: for combinations
>      >> >> from multiple list sources. My guess is that people need this
>      >> >> operation more often than mapping over multiple list. Another problem
>      >> >> is that you should be sure that all those lists have the same length.
>      >> >>
>      >> >> On Fri, Nov 18, 2011 at 10:38 AM, Barco You < <mailto:>> wrote:
>      >> >> > Hi Dmitry,
>      >> >> > What your suggested can really solve my problem, but it's not
>      >> >> > Tail-Recursion. The tail-recursed solution should look like this;
>      >> >> > map2(_Fun, [], []) ->
>      >> >> >    [];
>      >> >> > map2(Fun, L1, L2) ->
>      >> >> >    map2(Fun, L1, L2, []).
>      >> >> > map2(_Fun, [], [], L) ->
>      >> >> >    lists:reverse(L);
>      >> >> > map2(Fun, [H1 | T1], [H2 | T2], L) ->
>      >> >> >    map2(Fun, T1, T2, [Fun(H1, H2) | L]).
>      >> >> >
>      >> >> > However, I'm still disappointed with the list comprehension which is
>      >> >> > different from what I intuitively imagine about it.
>      >> >> >
>      >> >> > Regards,
>      >> >> > Barco
>      >> >> > On Fri, Nov 18, 2011 at 1:49 PM, Dmitry Demeshchuk
>      >> >> > < <mailto:>>
>      >> >> > wrote:
>      >> >> >>
>      >> >> >> My guess is you have to zip them together, or just write a
>      >> >> >> tail-recursed function:
>      >> >> >>
>      >> >> >> map2(Fun, [H1 | T1], [H2 | T2]) ->
>      >> >> >>    [Fun(H1, H2) | map2(Fun, T1, T2)];
>      >> >> >> map2(Fun, [], []) ->
>      >> >> >>    [].
>      >> >> >>
>      >> >> >> The second option definitely isn't a list comprehension, but it
>      >> >> >> requires less memory and has lesser complexity.
>      >> >> >>
>      >> >> >> On Fri, Nov 18, 2011 at 9:45 AM, Barco You < <mailto:>>
>      >> >> >> wrote:
>      >> >> >> > Dear Erlangers,
>      >> >> >> >
>      >> >> >> > I hope to get a list from two lists like this:
>      >> >> >> > [{a1,b1}, {a2,b2}, {a3,b3}] <-     [a1, a2 a3],  [b1, b2,
>      >> >> >> > b3].
>      >> >> >> > But if I use list comprehension, I got:
>      >> >> >> > 10>  [{D1,D2} ||  D1 <- [a1,a2,a3], D2 <- [b1,b2,b3]].
>      >> >> >> > [{a1,b1},
>      >> >> >> >  {a1,b2},
>      >> >> >> >  {a1,b3},
>      >> >> >> >  {a2,b1},
>      >> >> >> >  {a2,b2},
>      >> >> >> >  {a2,b3},
>      >> >> >> >  {a3,b1},
>      >> >> >> >  {a3,b2},
>      >> >> >> >  {a3,b3}]
>      >> >> >> >
>      >> >> >> > So, my questions is how to comprehend list in synchronous way in
>      >> >> >> > order
>      >> >> >> > to
>      >> >> >> > get what I want, rather than to compose the elements from two
>      >> >> >> > lists
>      >> >> >> > in
>      >> >> >> > all
>      >> >> >> > possible situations.
>      >> >> >> >
>      >> >> >> > Thank you,
>      >> >> >> > Barco
>      >> >> >> > _______________________________________________
>      >> >> >> > erlang-questions mailing list
>      >> >> >> >  <mailto:>
>      >> >> >> > http://erlang.org/mailman/listinfo/erlang-questions
>      >> >> >> >
>      >> >> >> >
>      >> >> >>
>      >> >> >>
>      >> >> >>
>      >> >> >> --
>      >> >> >> Best regards,
>      >> >> >> Dmitry Demeshchuk
>      >> >> >
>      >> >> >
>      >> >>
>      >> >>
>      >> >>
>      >> >> --
>      >> >> Best regards,
>      >> >> Dmitry Demeshchuk
>      >> >
>      >> >
>      >>
>      >>
>      >>
>      >> --
>      >> Best regards,
>      >> Dmitry Demeshchuk
>      >
>      >
>
>
>
>     --
>     Best regards,
>     Dmitry Demeshchuk
>
>
>
>
> _______________________________________________
> erlang-questions mailing list
> 
> http://erlang.org/mailman/listinfo/erlang-questions





More information about the erlang-questions mailing list