John,
Maxima's list operations are all non-destructive (except for explicit
assignments to list elements, e.g. list[23]: 5). This means they must copy
the whole list in many cases. The documentation of endcons in the Maxima
manual is actually fairly clear on this: "Returns a *new list* consisting of
the elements of list followed by expr. " (
http://maxima.sourceforge.net/docs/manual/en/maxima_37.html) It is
unfortunately not so clear in other cases where there might be as much or
more doubt, e.g. 'delete' (also non-destructive).
Note that endcons, even if it didn't copy the whole list, would still have
to *traverse* the whole list since Maxima uses singly-linked lists (as does
Lisp) so you would still have the n^2 behavior.
-s
On Sun, Sep 7, 2008 at 11:39 PM, John Lapeyre <john.lapeyre at gmail.com>wrote:
> I think the Maxima manual should mention somewhere to be
> careful about using endcons, because it makes a copy of the
> list, rather than cons which doesn't make a copy. If
> possible you should either build the list in the reverse
> order or make a final call to reverse. This is certainly
> common knowledge to lisp programmers and Maxima developers.
>