Re: `append' vs. `nconc'

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
>
>> You must remember the literal/immutable status of
>> each item at each level.
>>
>> Since you are incapable of remembering it, you
>> should assume that the whole input data is immutable
>> and write purely functional code (ie. use append,
>> not nconc) in general.
>
> OK, so you use `nconc' when you yourself create the
> lists by hand and thus know they are not empty, all
> the while using `list' and not ', and when done you
> assign the result to a variable associated with a list
> INSTEAD of using `nconc' directly because that
> variable can hold the empty list, i.e. nil, which
> `nconc' contrary to `append' cannot handle. And you do
> this to save time!

nconc can handle nil.  But in that case, it doesn't modify it! It just
return the nconc'ed list:

(nconc nil nil (list 1 2 3) nil (list 3 4 5) nil)
--> (1 2 3 3 4 5)

(let ((list nil))
   (list (nconc list nil (list 1 2 3) nil (list 3 4 5) nil)
         list))
--> ((1 2 3 3 4 5) ; returned
     nil) ; list is still bound to nil which cannot be mutated.

(let ((list nil))
   (list (setf list (nconc list nil (list 1 2 3) nil (list 3 4 5) nil))
         list))
--> ((1 2 3 3 4 5)  ; returned and set to list
     (1 2 3 3 4 5)) ; list has been set with setf, so it's ok.

The only case where you could forget the setf, is when you just return
the nconc'ed result:

    (defun f (list to-add)
      (setf list (nconc list to-add))
      list)

can be written just:

    (defun f (list to-add)
      (nconc list to-add))

But in such a case, notice that you will have to bind or use the result
of f:

   (let ((list (list 1 2 3)))
     (setf list (f list (list 4 5 6)))
     list)
   --> (1 2 3 4 5 6)

It's like with delete, but for the opposite reason: delete cannot
transform a cons cell into the symbol nil:

    (delete 1 (list 1)) --> nil

But in anycase, it is not specified how delete (or delq) modifies the
list structure, so even:

     (let ((list (list 1 2 3 4 5)))
        (delete 3 list)
        list)

is not guaranteed to return: (1 2 4 5)

Instead, you have to write:

     (let ((list (list 1 2 3 4 5)))
        (setf list (delete 3 list))
        list)
     --> (1 2 4 5)

to ensure that list is bound to the wanted result of delete.

It is general: when you have a function that mutate a structure and
return the new structure, if the exact way how it mutates it is not
specified or if it cannot always mutate it (eg for lists, when there's
an impossible transition nil <-> cons cell), you have use the result of
the function and cannot count on the mutation.

So, to use a non-mutating function:

    (setf list (remove element list))
    (setf list (append list tail))

and to use a mutating function:

    (setf list (delete element list))
    (setf list (nconc list tail))

In both cases you must rebind the result.


> Now I got it right!

almost. ;-)

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk