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

Richard O'Keefe raoknz@REDACTED
Tue Sep 17 00:25:37 CEST 2019


Briefly, the problem with
append(Xs, Ys) when is_list(Ys) ->
    combine(Xs, Ys).
is that is_list/1 ***ISN'T A TYPE CHECK FOR LISTS***.
It is misnamed.
is_list([_|_]) -> true;
is_list([])    -> true;
is_list(_)     -> false.
Try is_list([a|b]).
The result is true, despite [a|b] not being a list.
Unsurprisingly, (LISTP '()) and (LISTP '(1 . 2)) are
true in Common Lisp.   There is an interesting
difference between Common Lisp and Scheme:
(list? '(1 . 2)) is false in Scheme.  But the
Scheme function takes O(|list|) time.

Oddly enough, since Erlang is strict and functional,
it *would* be possible for Erlang to tag pairs whose
tail is a proper list differently from pairs whose
tail is *not* a proper list, with small constant
overhead.  *That* is what it would take to have an
affordable is_really_a_well_formed_list/1.


On Tue, 17 Sep 2019 at 01:54, zxq9 <zxq9@REDACTED> wrote:

> On 2019/09/16 11:49, Richard O'Keefe wrote:
> > The fact that L is a well-formed list is verified N times,
> > for a total cost O(N * |L|).  But with the current definition,
> > the cost is O(N), independent of |L|.
>
> Hm... just to beat a dead horse...I suppose we could get away with a
> single check:
>
>    -export([append/2]).
>
>    append(Xs, Ys) when is_list(Ys) -> combine(Xs,Ys).
>
>    combine([X | Xs], Ys) -> [X | combine(Xs, Ys)];
>    combine([],       Ys) -> Ys.
>
> > I will say that I've been using languages in the Lisp family for
> > a little over 40 years, and this has been the very *least* of my
> > problems.
>
> The whole issue boils down to the above. I can see some trivial merit in
> doing a type check over Ys at the outset (since we'll crash on bad Xs in
> the actual procedure) but this business of moving to the last element to
> check whether the list is properly formed is both insane and almost
> certainly a legacy code killer, as there are a handful of systems out
> there that depend on being able to manipulate improper lists for
> whatever reason.
>
> I didn't follow this thread closely, but I'm surprised I didn't see
> doing a single type check on entry as a possibility. What issues would
> make this a bad idea?
>
> -Craig
> _______________________________________________
> 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/20190917/ab339fc6/attachment.htm>


More information about the erlang-questions mailing list