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

Richard O'Keefe raoknz@REDACTED
Mon Sep 16 04:49:51 CEST 2019


Your proposed fix may be easy and small, but it is not a fix.

Why do you suppose append/1 wasn't written *this* way?

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

app([Xs|Xss]) -> app(Xs, app(Xss));
app([])       -> [].

I coded this up, using app instead of append, and got this:

2> app:app([[],[a|b]]).
** exception error: no function clause matching app:app(b,[]) (app.erl,
line 4)
     in function  app:app/2 (app.erl, line 4)
     in call from app:app/1 (app.erl, line 7)

That would seem to be what you are after, and it's *simpler* than the
existing code.  So what is the point?

Let L be a well formed list, and consider

   append([[1],[2],...,[N],L])

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|.

Oddly enough, there *is* a way to check that a list is well formed
in a guard.  Let's try this.

append([Xs]) when length(Xs) >= 0 -> Xs;
append([Xs|Xss]) -> Xs ++ append(Xss);
append([]) -> [].

This actually *would* be a "fix", and the cost would be
O(N + |L|) instead of O(N * |L|).
But that would make append([Xs,Ys]) inconsistent with
Xs++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.

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

> Michal,
> i really prefer crashing than garbage in, garbage out policy.
> also it would be nice if someone from OTP team confirms if stdlib has
> "garbage in garbage out" policy. i can certainly see benefits of it but in
> this case fix is easy and small.
>
> On Sun, Sep 15, 2019 at 7:54 PM Michał Muskała <michal@REDACTED> wrote:
>
>> My understanding is that for most functions in the Erlang standard
>> library, if you don't uphold the contract the documentation specifies the
>> function can crash, but it could also return whatever - in short "garbage
>> in, garbage out" applies.
>>
>> Michał.
>> On 15 Sep 2019, 18:45 +0100, 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
>>
>> _______________________________________________
> 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/87c9e99f/attachment.htm>


More information about the erlang-questions mailing list