Re: Manipulating lists somewhere in the middle (index-based)

[Pascal J. Bourguignon]

florian <lorian@fsavigny.de> writes:

> I know there was a similar discussion yesterday (see
> http://groups.google.de/group/gnu.emacs.help/browse_thread/thread/2fc2d1ea2229f3bc),
> but that involved examining elements.
>
> I am actually just wondering whether I reinvented the wheel in writing
> two (non-destructive) functions:
>
> (drop-nth 2 '(1 2 3 4 5))
> => (1 2 4 5)

Could be done with:

    (require 'cl)
    (remove-if (constantly t) '(1 2 3 4 5 6) :start 2 :end 3)
    --> (1 2 4 5 6)


> (squeeze-in-at 2 "three" '(1 2 4 5))
> => (1 2 "three" 4 5)

Usually called insert.  Here are the destructive versions of the above forms:

    (require 'cl)

    (let ((list (list 1 2 3 4 5 6)))
      (setf list (delete-if (constantly t) list :start 2 :end 3))
      list)
    --> (1 2 4 5 6)

    (let ((list  (list 1 2 3 4 5)))
      (push "three" (nthcdr 2 list))
      list)
    --> (1 2 "three" 3 4 5)


> My function definitions are probably not particularly interesting (if
> anybody thinks they are, just let me know - they both simply work by
> building a new list and returning it), but what I am wondering about
> is this: when looking at the linked-paired-boxes notation the Elisp
> manual uses to explain lists:
>
>   --- ---      --- ---      --- ---
>  |   |   |--> |   |   |--> |   |   |--> nil
>   --- ---      --- ---      --- ---
>    |            |            |
>    |            |            |
>     --> fir       --> oak      --> maple
>
> [slightly modified]
>
> it is actually very tempting to suspect there must be a way to
> directly make the pointer from the cdr of "fir" point to the car of
> the "maple" element and making the car of "oak" point to nil instead,
> thus dropping the element from the list and getting (fir maple) as the
> result.
>
> Or, the other way round, it looks as if there could be a way to make
> the pointer of the "oak" element point to a new cons cell, which has
> "birch" as its car, and whose cdr we have point to the car of the
> "maple" element, so as to get the list (fir oak birch maple).
>
> Is there in fact some way to mess with these pointers, or is that a
> purely didactic concept? Thanks for any input, it is really just
> curiosity about Elisp!


Usually, lisp list processing functions come in two versions, one
"destructive" and another "non destructive".  Or, more exactly, one
"non-consing" and another that conses the result:

destructive      non-consing     nreverse    modifies the original list
non-destructive  "consing"       reverse     doesn't modify the original

Non-consing functions (those having the side effect of possibly
modifying the original list) have usually a name prefixed by N.

    nreverse / reverse
    nsubst / subst
    nunion / union

but there are some irregularities, for historical reasons:

    nconc / append
    delete / remove


Notice that a non-consing doesn't necessarily modify the original list
(the destruction is not mandatory).  What it does is not to allocate
memory.  So:

    (let ((expr (copy-tree '(+ (* y 3) z)))) ; must make a modifiable 
                                             ; copy of the quoted literal
       (nsubst '2 'x expr) ; because nsubst potentially modifies expr.
       expr)

won't modify the cons cells of expr, since there's no occurence of x
in it; nsubst in this case just returns expr.


Finally, the primitives to modify a cons cell are rplaca and rplacd
(those are the historical names; in emacs lisp, they aliased to setcar
and setcdr).  But it's easier to use setf:

    (require 'cl)

    (let ((x (cons 1 2)))
      (setf (car x) 11
            (cdr x) 22)
      x)
    --> (11 . 22)

So you can modify your lists or other structures made of cons cells.



A good exercise would be to implement a doubly linked list.  You'd
need three pointers at each node, one to the previous, one to the
next, and one to the item.  So you need two conses to hold these three
pointers.  For example: (defun make-node (i p n) (cons i (cons n p)))



head -----+              NIL
          |               ^
          v               |
+---+   +---+---+   +---+---+
| 1 |<--| * | * |-->| * | * |
+---+   +---+---+   +---+---+
          ^           |
          |           |
          +---------------+
                      |   |
          +-----------+   |
          |               |
          v               |
+---+   +---+---+   +---+---+
| 2 |<--| * | * |-->| * | * |
+---+   +---+---+   +---+---+
          ^           |
          |           |
          +---------------+
                      |   |
          +-----------+   |
          |               |
          v               |
+---+   +---+---+   +---+---+
| 3 |<--| * | * |-->| * | * |
+---+   +---+---+   +---+---+
          ^           |
          |           v
tail -----+          NIL

The doubly-linked-list is represented as a record holding the head and
the tail (perhaps a cons cell), but you could also add eg. the length
of the list.

Implement functions to insert and remove elements after or before
other elements, or at a given position; to concatenate two
doubly-linked-lists; to map over them in either direction ; to compute
the length; etc.

An alternative is to have the last node point to the first (thru the
next pointer) and the first node point to the last (thru the previous
pointer), making it a circular doubly-linked list, so you need only a
pointer to the head instead of one to the head and one to the tail, so
you don't need the record.

Use:

    (require 'cl)
    (setf print-circle t)

to be able to print circular structures without infinite loops.




PS: you could just as well put (require 'cl) in your ~/.emacs and
    forget about it...
-- 
__Pascal Bourguignon__