Lisp

53 readers

3 users here now

founded 1 year ago

MODERATORS

rglullis

defmacro

What does actually happen in destructive operations on lists and vectors? (alien.top)

submitted 1 year ago by Typhoonfight1024@alien.top to c/lisp

2 comments fedilink hide all child comments

For example, suppose that I have a list/vector of integers named dt, and I want to remove elements with the value 70 there. In Common Lisp it would be:

 (setf dt (remove 70 dt))

My question is, which scenario is actually happening here?

All original elements of dt are erased. After that, all elements of dt are remade entirely from ground up, elements by elements, excluding the removed value that is 70.
The only affected elements are those with the value of 70. Only those elements are modified in any way (in this case removed). All other elements are left untouched at all, except that maybe they ‘change positions’ to fill the place of the removed elements.
The original list/vector with 70s loses any association with the variable dt. Then a new list/vector without 70s is assigned to dt.

you are viewing a single comment's thread
view the rest of the comments

[–] zyni-moe@alien.top 1 points 1 year ago

In no case does remove modify the original object or any of its elements.

remove will traverse the object looking for elements which match thing to be removed

if are no such elements it may return either a copy of the original object with same type or the original object;
if are such elements it will return a new object which has those elements removed but which is same type as original object..

In second case the returned object may share structure with original object. This really applies only for lists.

Example for lists, it is allowed that

(let ((x (list 1 2 3)))
  (eq (remove 1 x) (cdr x)))

may return true. Is actually unlikely it will do so, because implementation of remove which can do this check would be quite hard to see how it would be better, but is allowed to be the case.

Here is implementation of simple version of remove which works only on lists and which does not ever share:

(defun remove-from-list (e l)
  (loop for thing in l
        when (eql thing e) collect thing))

Here is version which does share, you can see why this is nasty.

(defun remove-from-list (e l)
  (labels
      ((rfll (lt et)
         (cond
          ((null lt)                    ;done with list
           '())
          ((null et)                    ;done with es
           lt)
          ((eq lt et)                   ;hit first e
           (rfll (rest lt) (member e (rest lt))))
          (t                            ;are es but not yet
           (cons (first lt) (rfll (rest lt) et))))))
    (rfll l (member e l))))

Perhaps there are better approaches than this one: certainly there are which can be made tail recursive or iterative, but need to keep looking to know when to copy is expense.