<div dir="ltr"><div class="gmail_default" style="font-family:monospace,monospace">This particular issue goes back nearly 60 years.</div><div class="gmail_default" style="font-family:monospace,monospace">Here is the traditional definition of "append", using Erlang syntax.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">append([X|Xs], Ys) -> [X | append(Xs, Ys)];</div><div class="gmail_default" style="font-family:monospace,monospace">append(_,      Ys) -> Ys.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">This was tightened up in more recent Lisp systems to the equivalent of</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">append([X|Xs], Ys) -> [X | append(Xs, Ys)];</div><div class="gmail_default" style="font-family:monospace,monospace">append([],     Ys) -> Ys.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">To this day, if you fire up a Common Lisp REPL, you can get this</div><div class="gmail_default" style="font-family:monospace,monospace">* (append '(x) 'y)<br><br>(X . Y)</div><div class="gmail_default" style="font-family:monospace,monospace">That was CMU Common Lisp 21d.  You get the same in Scheme.</div><div class="gmail_default" style="font-family:monospace,monospace">And in Erlang,</div><div class="gmail_default" style="font-family:monospace,monospace">1> [a]++b.<br>[a|b]</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">The point of this is that you want the cost of (append Xs Ys) to be</div><div class="gmail_default" style="font-family:monospace,monospace">O(length(Xs)).  We really really don't want it to be O(length(Xs++Ys)).</div><div class="gmail_default" style="font-family:monospace,monospace">Now suppose we did</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">append([X|Xs], Ys) -> [X | append(Xs, Ys)];</div><div class="gmail_default" style="font-family:monospace,monospace">append([],     Ys) when is_list(Ys) -> Ys.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">What good would that actually do?  is_list is not well named.<br></div><div class="gmail_default" style="font-family:monospace,monospace">3> is_list([a|b]).<br>true</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">So instead of append([a], b) -> [a|b] we would still have</div><div class="gmail_default" style="font-family:monospace,monospace">append([], [a|b]) -> [a|b].  The only way to ensure that the result</div><div class="gmail_default" style="font-family:monospace,monospace">of append is a well formed list is to check the *entire* spine of the</div><div class="gmail_default" style="font-family:monospace,monospace">second argument, and now we have this big cost we really wanted to avoid.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">I've been talking about the traditional "append" function.  You were</div><div class="gmail_default" style="font-family:monospace,monospace">talking about append/1.  But it's the same thing.  Instead of</div><div class="gmail_default" style="font-family:monospace,monospace">append([[a],b]) -> [a|b], we'd still have append([[],[a|b]]) -> [a|b].</div><div class="gmail_default" style="font-family:monospace,monospace">Inserting a call to is_list/1 would *only* add overhead without doing</div><div class="gmail_default" style="font-family:monospace,monospace">anything practical to address the issue.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">Erlang's solution is the type checker.  This is also the solution adopted</div><div class="gmail_default" style="font-family:monospace,monospace">by SML, O'CAML, Haskell, Clean, Goedel, Mercury, the DEC-10 Prolog type</div><div class="gmail_default" style="font-family:monospace,monospace">checker (originally inspired in part by a desire to prove theorems about</div><div class="gmail_default" style="font-family:monospace,monospace">Prolog's append/3 that are not in fact sound without a type checker) and</div><div class="gmail_default" style="font-family:monospace,monospace">several other languages in the Lisp family.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, 16 Sep 2019 at 05:45, Karlo Kuna <<a href="mailto:kuna.prime@gmail.com">kuna.prime@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Hello,<br></div><div><br></div><div>i have found surprising  behavior of function lists:append/1: </div><div><br></div><div>spec and documentation  are in a agreement that this function should accept lists of lists ( [List] ) , </div><div>and return list of T ( [T] ), however when we use function like: </div><div> </div><div>     lists:append([a]) %wrong input parameter </div><div>one gets: </div><div>     a  % wrong type of a return </div><div><br></div><div>implementation assumes correct type: </div><div><br></div><div>append([E]) -> E; % E is not checked for type <br>append([H|T]) -> H ++ append(T);<br>append([]) -> [].<br></div><div><br></div><div>simple solution could be: <br><br>lists:append([E]) when is_list(E) -> E <br><br></div><div>am i missing something? </div><div><br></div></div>
_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" rel="noreferrer" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
</blockquote></div>