Re: Easy to add with push but not to the end of a list

[Marcin Borkowski]

On 2022-11-29, at 08:56, Heime <heimeborgia@protonmail.com> wrote:

> Programming has got nothing to do with engineering or craft.

What is it, then?  (I'm genuinely curious about your opinion.)

>> Singly linked lists are a tool. They are simple, lightweight,
>> and appropriate for keeping things in sequence, and for adding
>> things at the front. Not at the end.
>
> Stefan mentioned using reverse to put it into another list.  If needed
> the execution time would not be much different than actually place
> new elements at end of list.

The difference is that you keep adding items at the front and then
reverse the list /once/.

Another pattern you might use is to ditch lists and keep the items in
a temporary buffer, keeping point at its end (which is easy with
`insert'), and then traverse the buffer to gather the results as needed.
You might even want to keep them in a buffer as a printed representation
of a list, and then read it, using the Elisp parser.  (I don't know what
function would help with that, but I'm pretty certain such a function
exists.)  Not sure how efficient this would be, but I'd guess it could
be pretty good with really large number of items.

Yet another option would be to keep the whole list in some variable, but
use another variable (say, `last') as a "pointer" to the last cons of
that list.  Then, you can define `fast-append' like this:

(defvar last nil)
(defvar my-list nil)

(defun fast-append (el)
  "Append EL at the end of `my-list' in O(1) time."
  (if (not my-list)
      (setf my-list (cons el nil)
            last my-list)
    (setf (cdr last) (cons el nil)
          last (cdr last))))

This then would be O(1).

>> Core library functions express idioms. They are expected to
>> help people to find patterns on how to use tools appropriately
>> (it's not much different from tools: a screwdriver has a
>> handle, which spells "grip me here, please").
>>
>> Adding a function to core (say `hsup') which suggests that
>> it is as easy to push something at the end of a list would
>> be misleading people to hold the screwdriver (or the knife!)
>> at the wrong end and hurt themselves.
>
> Nobody will get hurt.  Just inefficient for long lists or for
> large number of calls.

Every time someone appends to the end of a singly linked list, a cute
kitty dies...

;-)

-- 
Marcin Borkowski
http://mbork.pl