behavior of lists:append/1

classic Classic list List threaded Threaded
24 messages Options
12
mko
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

mko
Hi, Richard,

Thanks for explaining the fascinating tradition behind append/1 in Lisp and Prolog. 

I totally agree with you on the simplicity and performance aspect of append/1 and append/2. I doesn’t make sense at all to add the O(n) check for “proper list”.

I remember when I was following a beginner tutorial on Prolog, I’ve found the append/1 confused me same as Karlo.  I think most people including me is confused append/1 with something like flat (not lists:flatten/1) or chain in other languages like the the new addition: flat method of Array in Javascript:

>[[1, 2], 3].flat()
 [1, 2, 3]

>[[1, [2]], 3].flat()
[1, [2], 3]

>[1].flat()
[1]

>[].flat()
[]

it only “flat” once instead “flat” all the way like erlang lists:flatten/1 does

I think it fit to into people’s mindset about “flat once” of an ordered collection and return the same type.

simple implementation in erlang would be:

flat([]) -> [];
flat([[]|T]) -> flat(T);
flat([[H1|T1]|T]) -> [H1|flat([T1|T])];
flat([H|T]) -> [H|flat(T)].

>flat([[1,2],3]).
[1,2,3]

>flat([[1, [2]], 3]).
[1,[2],3]

>flat([1]).
[1]

>flat([]).
[].

The only thing inconsistent is that as you pointed out several times there's no easy way to check the list is a “proper list” without walking to the end of the list, 

> flat([1|2]).
** exception error: no function clause matching lists2:flat(2) 

but I think it’s ok to skip the “proper list” checking and let dialyzer or programmer handle it as you suggested, and so maybe it’s good to add flat/1 to the lists module and make it a clear separation  of append/1 and  flat/1 which maybe a concept a lot of programmer already familiar with .

mko

On 19/09/2019, at 8:29 PM, Richard O'Keefe <[hidden email]> wrote:

"Not checking for whether something is a properly formed list (the whole
objection some have is that append/2 should be able to accept an
improper list as the second argument) but merely checking whether the
second argument is a list of any form at all."

But what the heck is the point of *that*?
Why is it important for  [a] ++ c to fail
but OK for [a] ++ [b|c] to succeed?
I'm sorry, but that makes no sense to me at all.




On Thu, 19 Sep 2019 at 18:58, zxq9 <[hidden email]> wrote:
On 2019/09/19 10:33, Richard O'Keefe wrote:
> I'm sorry, but what O(1) runtime check are we talking about here?
> I don't know of any O(1) way to test "is this a proper list" in
> Erlang.

Not checking for whether something is a properly formed list (the whole
objection some have is that append/2 should be able to accept an
improper list as the second argument) but merely checking whether the
second argument is a list of any form at all.

A single is_list/1 check guarding the leading clause can do that.

The discussion has gone through:

A1: "The typespec says both arguments must be lists"
B1: "Use Dialyzer"

A2: "The check should be dynamic at runtime"
B2: "Checking for *proper* lists is too much overhead"

A3: "We should accept improper lists as a second argument"
B3: "Then is_list/2 could check the 2nd arg on entry only"

A4: "Some people use append/2 to *construct* improper lists"
B4: "Then why do we even have a typespec at all?"

My position is that B2 and A3 are valid, and B3 is a reasonable
compromise that shouldn't break legacy code. I think A4 is unreasonably
inconsistent, though, and would wonder why we're even going to have a
typespec.

-Craig
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

zxq9-2
In reply to this post by Richard O'Keefe
On 2019/09/19 17:29, Richard O'Keefe wrote:
> "Not checking for whether something is a properly formed list (the whole
> objection some have is that append/2 should be able to accept an
> improper list as the second argument) but merely checking whether the
> second argument is a list of any form at all."
>
> But what the heck is the point of *that*?
> Why is it important for  [a] ++ c to fail
> but OK for [a] ++ [b|c] to succeed?
> I'm sorry, but that makes no sense to me at all.

You'd have to ask the OP.

The only reason I can think of would be to make sure I didn't change
something trivial in code somewhere and wind up passing a record or map
to append/2 without realizing it (crash on the first run/test/whatever).
But this is what I use Dialyzer for anyway.

The point of the thread was the feasibility of making a runtime check to
guarantee a crash if the arguments weren't lists instead of merely going
with "garbage in, garbage out". I can see some sense to that, but
wouldn't prioritize append/2 over all the other functions that expect
lists and *might* receive junk -- I certainly wouldn't want to make ALL
functions have runtime type checks!

The only place I put dynamic checks in my own code is when I'm
sanitizing data coming in from the outside. Everything else gets Dialyzed.

-Craig
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

Raimo Niskanen-11
In reply to this post by zxq9-2
On Thu, Sep 19, 2019 at 06:54:29AM +0900, zxq9 wrote:

> On 2019/09/18 21:00, Raimo Niskanen wrote:
> > On Tue, Sep 17, 2019 at 11:25:11PM +0900, zxq9 wrote:
> >> On 2019/09/17 22:13, Raimo Niskanen wrote:
> >>> On Mon, Sep 16, 2019 at 10:53:57PM +0900, zxq9 wrote:
> >>> No.
> >>>
> >>> lists:append/2 can be used and *is* used by existing code to construct
> >>> improper lists.  It would break backwards compatibility.
> >
> > ...to construct improper lists even as in appending a tail element (that is
> > need not be a list) to a list...
>
> At least here we can put down a line and say "that's a violation of the
> typespec", because it is:
> http://erlang.org/doc/man/lists.html#append-2

You are right.

I dug up this discussion:
    http://erlang.org/pipermail/erlang-questions/2013-March/073022.html

And from that I draw these conclusions:
* The type specs and documentation describe the intention of the API
* If the arguments follow the type spec, so will the return value
* If not, it will not, but there is no guarantee for e.g an exception
* Code may be more lenient that its type spec

So, if you use lists:append/1,2 to construct an improper list you will get
a Dialyzer warning, even though the code works.

We will not change the implementation of lists:append/1,2 for effeciency
and legacy reasons.  If anything should change it should be the type spec
and documentation, but I see no good reason why.  Now you get a warning
from Dialyzer for "bad style" according to some definition of it, which
many think is a good thing.

Dialyzer only makes guarantees about code that follows the type specs.
Code that does not follow the type specs might work anyway.

I suspect this whole thread originates in a misunderstanding about what
type specs specify and not...

>
> So if we want to continue to use append/2 to *create* improper lists
> (which I've never once encountered anywhere in the last decade, but
> maybe you've got some examples of super wizard code where this is
> necessary?) then the typespec should be changed, otherwise I think it
> isn't unreasonable to do at +O(1) cost at runtime what Dialyzer would
> do, or just leave things as they are and actively discourage deliberate
> construction of improper lists via append/2.
>
> I'm not particularly opposed to changing the typespec to say "List2 can
> be whatever because who cares whether lists are lists or not? Let's
> ditch type sanity because a handful of people feel like it! WOOO!" but I
> *do* believe it is inconsistent to the extreme to say "Well, we're going
> to have Dialyzer (and all users who read the documentation... har har
> har! Joke's on them!) believe that both arguments must be lists!" and
> then in unofficial -- but heavily referenced -- discussion have an OTP
> developer say "well, append/2 is used by some people to deliberately
> construct improper lists, so let's just ignore the discussion entirely
> even though there is actually a way to efficiently check this at runtime".
>
> -Craig

--

/ Raimo Niskanen, Erlang/OTP, Ericsson AB
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

zxq9-2
On 2019/09/23 17:08, Raimo Niskanen wrote:

> On Thu, Sep 19, 2019 at 06:54:29AM +0900, zxq9 wrote:
>> On 2019/09/18 21:00, Raimo Niskanen wrote:
>>> On Tue, Sep 17, 2019 at 11:25:11PM +0900, zxq9 wrote:
>>>> On 2019/09/17 22:13, Raimo Niskanen wrote:
>>>>> On Mon, Sep 16, 2019 at 10:53:57PM +0900, zxq9 wrote:
>>>>> No.
>>>>>
>>>>> lists:append/2 can be used and *is* used by existing code to construct
>>>>> improper lists.  It would break backwards compatibility.
>>>
>>> ...to construct improper lists even as in appending a tail element (that is
>>> need not be a list) to a list...
>>
>> At least here we can put down a line and say "that's a violation of the
>> typespec", because it is:
>> http://erlang.org/doc/man/lists.html#append-2
>
> You are right.
>
> I dug up this discussion:
>      http://erlang.org/pipermail/erlang-questions/2013-March/073022.html
>
> And from that I draw these conclusions:
> * The type specs and documentation describe the intention of the API
> * If the arguments follow the type spec, so will the return value
> * If not, it will not, but there is no guarantee for e.g an exception
> * Code may be more lenient that its type spec
>
> So, if you use lists:append/1,2 to construct an improper list you will get
> a Dialyzer warning, even though the code works.
>
> We will not change the implementation of lists:append/1,2 for effeciency
> and legacy reasons.  If anything should change it should be the type spec
> and documentation, but I see no good reason why.  Now you get a warning
> from Dialyzer for "bad style" according to some definition of it, which
> many think is a good thing.
>
> Dialyzer only makes guarantees about code that follows the type specs.
> Code that does not follow the type specs might work anyway.
>
> I suspect this whole thread originates in a misunderstanding about what
> type specs specify and not...

Makes sense.

I tend to follow Dialyzer almost religiously on projects where I need
hot upgrades, so am probably giving its returns too much weight.

I'll bookmark your response to reference the next time this conversation
pops up.

Regards
-Craig
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
12