Tail/Non tail recursion

[Richard A. O'Keefe]

Jilani Khaldi wrote:
	> Is there a better way to write this code
====>	> when there is a lot of elements in the list?
	
	> square([H|T]) -> [H*H | square(T)];
	> square([]) -> [].

Bengt Kleberg <Bengt.Kleberg@REDACTED> suggested, more or less,

	square(Numbers) -> lists:map(fun(X) -> X*X end, Numbers).

Using a higher order function so that you don't have to code the
recursion yourself is "better" in several ways, but I take it that
the key phrase was "when there is a lot of elements in the list".

The answer is to _measure_ it.

3> sq:t(d, 100000).
{650,100000}
5> sq:t(m, 100000).
{2990,100000}

That is, the first (direct) version was about 4.6 times faster,
and thus "better" for large numbers of elements.

Here's a transcript of Erlang running my test file.
f% erl
1> c(sq).
{ok,sq}
2> l(sq).
{module,sq}
3> sq:t(d, 100000).
{650,100000}
4> sq:t(u, 100000).
{430,100000}
5> sq:t(m, 100000).
{2990,100000}
6> {2990/650, 2990/430, 650/430}.
{4.60000,6.95349,1.51163}
7> halt().

We see that the lists:map version is 4.6 times slower than the
direct version, which is in term 1.5 times slower than an unrolled version.

On a different processor, or with a different version of Erlang, your
results might well be different, but the ratios are likely to be roughly
the same.  If the speed of such an operation is of the utmost importance,
then it might be worth going with an unrolled version, but the simple
direct version should normally be fast enough.

Here is the sq module.  It's not intended as an example of good Erlang
style, it's just what I typed in a hurry to do the job.

-module(sq).
-export([t/2]).

t(V, N) ->
    m(V, lists:duplicate(N, 28.0)).

m(V, L) ->
    {T0,_} = statistics(runtime),
    R = r(V, L),
    {T1,_} = statistics(runtime),
    {T1-T0, length(R)}.

r(d, L) -> d(L);
r(u, L) -> u(L);
r(m, L) -> lists:map(fun(X) -> X*X end, L).

d([H|T]) -> [H*H | d(T)];
d([])    -> [].

u([H1,H2,H3|T]) -> [H1*H1, H2*H2, H3*H3 | u(T)];
u([H1|T])       -> [H1*H1 | u(T)];
u([])           -> [].