[erlang-questions] Efficiency of a list construction

[Frédéric Trottier-Hébert]

I would dare say that tail recursion is not exactly important in this example.

In both cases, you basically end up creating a list, which will hold all the values of all messages. In one case, you will be creating a list of N elements to be carried on the stack, in the other case, you'll be having a stack that is about the size of N elements.

In the first case, you also have to reverse the list, in the other, you don't. It's not really a big deal IMO to use a call that is not tail recursive when what you are doing is building a list that is in the same order as the items happen. If you look into the stdlib, you'll see that the lists:map/2 function is (or was? haven't looked in a few versions) implemented in a non tail recursive manner. When you think of it, it kind of makes sense too; you give a list of the same size as before, in the right order, for similar speeds, and you'll be avoiding a call to a BIF (reverse/1) on top of it.

Now, in the case when you're building a list in a different order or where you basically create more data than necessary by avoiding recursion (ex.: a tail recursive fibonacci vs. a non tail recursive fibonacci), then tail recursion should be chosen, but I see nothing wrong with the flush/0 implementation of Kannan.

--
Fred Hébert
http://www.erlang-solutions.com



On 2011-05-20, at 06:50 AM, Vance Shipley wrote:

> Kannan,
> 
> No, it is not tail recursive.  This is:
> 
>     %% @spec() -> [term()]
>     %%
>     flush() ->
>     	flush([]).
> 
>     %% @hidden
>     flush(Msgs) ->
>     	receive
>     		Msg ->
>     			flush([Msg | Msgs]);
>     	after 17 ->
>     		Msgs
>     	end.
> 
> On Fri, May 20, 2011 at 03:45:19PM +0530, Kannan wrote:
> }  Is the following list construction an efficient one?
> }  
> }  flush() ->
> }      receive
> }  Msg ->
> }      [Msg|flush()]
> }      after 17 ->
> }      []
> }      end.
> 
> -- 
> 	-Vance
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions