[erlang-questions] behavior of lists:append/1

[Richard O'Keefe]

This particular issue goes back nearly 60 years.
Here is the traditional definition of "append", using Erlang syntax.

append([X|Xs], Ys) -> [X | append(Xs, Ys)];
append(_,      Ys) -> Ys.

This was tightened up in more recent Lisp systems to the equivalent of

append([X|Xs], Ys) -> [X | append(Xs, Ys)];
append([],     Ys) -> Ys.

To this day, if you fire up a Common Lisp REPL, you can get this
* (append '(x) 'y)

(X . Y)
That was CMU Common Lisp 21d.  You get the same in Scheme.
And in Erlang,
1> [a]++b.
[a|b]

The point of this is that you want the cost of (append Xs Ys) to be
O(length(Xs)).  We really really don't want it to be O(length(Xs++Ys)).
Now suppose we did

append([X|Xs], Ys) -> [X | append(Xs, Ys)];
append([],     Ys) when is_list(Ys) -> Ys.

What good would that actually do?  is_list is not well named.
3> is_list([a|b]).
true

So instead of append([a], b) -> [a|b] we would still have
append([], [a|b]) -> [a|b].  The only way to ensure that the result
of append is a well formed list is to check the *entire* spine of the
second argument, and now we have this big cost we really wanted to avoid.

I've been talking about the traditional "append" function.  You were
talking about append/1.  But it's the same thing.  Instead of
append([[a],b]) -> [a|b], we'd still have append([[],[a|b]]) -> [a|b].
Inserting a call to is_list/1 would *only* add overhead without doing
anything practical to address the issue.

Erlang's solution is the type checker.  This is also the solution adopted
by SML, O'CAML, Haskell, Clean, Goedel, Mercury, the DEC-10 Prolog type
checker (originally inspired in part by a desire to prove theorems about
Prolog's append/3 that are not in fact sound without a type checker) and
several other languages in the Lisp family.

On Mon, 16 Sep 2019 at 05:45, Karlo Kuna <kuna.prime@REDACTED> wrote:

> Hello,
>
> i have found surprising  behavior of function lists:append/1:
>
> spec and documentation  are in a agreement that this function should
> accept lists of lists ( [List] ) ,
> and return list of T ( [T] ), however when we use function like:
>
>      lists:append([a]) %wrong input parameter
> one gets:
>      a  % wrong type of a return
>
> implementation assumes correct type:
>
> append([E]) -> E; % E is not checked for type
> append([H|T]) -> H ++ append(T);
> append([]) -> [].
>
> simple solution could be:
>
> lists:append([E]) when is_list(E) -> E
>
> am i missing something?
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20190916/7b8b23b0/attachment.htm>