[erlang-questions] Efficiency of a list construction

[Richard O'Keefe]

Consider

	map(F, [X|Xs]) -> [F(X) | map(F, Xs)];
        map(_, []    ) -> [].

By the classical definition, this is not tail recursive.
The Prolog equivalent, however, _is_.

The reason the Prolog version is tail recursive is that it
can build a data structure with a hole in it [F(X) | Hole]
and pass the hole:

	map(F, [X|Xs], &Result) =>
	    *Result := [F(X) | Hole],
	    map(F, Xs, &Hole);
	map(F, [], &Result) =>
	    *Result := [].

And this would be safe even in Erlang because nobody (other
than the garbage collector) can ever see the hole.
This extended version of "tail recursion" applies when there
the last expression that the call occurs in is a data structure
construction.

The existing Erlang system *doesn't* support extended tail
recursion, largely for the sake of the garbage collector.
But it could, without any change to the source language
or its semantics.