Re: Walking a list

Dan Bensen <randomgeek@xxxxxxxxxxxxxx> writes:
The OP explicitly asked for the "Lisp way" of solving the problem,
which does require implicit pointers in the Lisp sense, and every
C programmer knows that multiple references can point to the same
memory location. So all the OP really needed to know was how to
do what they were describing.


Well, I hesitated to answer to the OP because he blatantly lied us,
since he mentionned singly and doubly linked lists, but the code he
showed cannot be list processing code in C (it could be in C++, but
he only mentionned C).


"Leslie P. Polzer" <leslie.polzer@xxxxxxx> wrote:
Suppose I want to keep track of the current element in a {singly,
doubly}-linked list (that might be circular) and at some point cleanly
advance it by one or more steps.

In C I'd do something like that:

list* p = LIST; /* let p initially point to the list head */
p++; /* might also be p += 5; */
/* assertion: p always points at the current element of the list */

And would walk it by just saying

while (p++); /* this obviously doesn't work out for circular lists,
but let's keep things simple */

What's the idiom for this stuff in Lisp? I'm sure there must be some
smug solution
that, as usual, eludes me. Thanks, folks.


Now, if we ignore almost totally the request of the OP, we could say
that one can easily walk a list in lisp. After all, LISP means LISt
Processing.

In the case of a simple singly-linked list:

(let ((p (list 1 2 3 4 5)))
(loop
:while p
:do (process (car p))
:do (pop p)))

or:

(let ((p (list 1 2 3 4 5)))
(loop
:for item :in p
:do (process item)))

or:

(let ((p (list 1 2 3 4 5)))
(dolist (item p)
(process item)))

or:

(map nil (function process) (list 1 2 3 4 5))

etc... There is no single idiom in lisp....



In the case of a circular singly-linked list:

(defun make-circular (list) (setf (cdr (last list)) list))

(let ((p (make-circular (list 1 2 3 4 5))))
(loop
:while (some-condition)
:do (process p)
:do (pop p)))







In the case of doubly-linked lists, it would depend on the data
structure used for them.

For example, with a non-circular dll:

(defstruct dll next previous item)

(defun dll-first (dll)
(loop
:until (null (dll-previous dll))
:do (setf dll (dll-first (dll-previous dll)))
:finally (return dll)))

(defun dll-list (&rest items)
(loop
:with dll = (make-dll)
:while items
:do (setf (dll-next dll) (make-dll :item (car items) :previous dll)
dll (dll-next dll))
:finally (return (dll-first dll))))


Then you can write:

(let ((p (dll-list 1 2 3 4 5)))
(loop
:while p
:do (process (dll-item p))
:do (setf p (dll-next p))))

or:

(let ((p (dll-list 1 2 3 4 5)))
(loop
:for cur = p :then (dll-next cur)
:do (process (dll-item cur))))

etc...



I still don't see the point of the OP's question...


On the other hand, in C I'd write something like:

{ dll* p=dll_list(5,1,2,3,4,5);
while(!dll_empty_p(p)){
process(dll_item(p));
p=dll_next(p); }}

so...



--
__Pascal Bourguignon__ http://www.informatimago.com/

NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
.

Relevant Pages

  • Re: Fundamentals of Lisp efficiency?
    ... your lisp will likely drop dead. ... If your code has a `main loop' from which all subroutines ... Especially for lists. ... Naive floating point in Common Lisp is ...
    (comp.lang.lisp)
  • Re: Multiplication of lists
    ... I'm rather new to LISP as you might be able to tell from my simple ... I wan't to write a function that multiplies a list of numbers by all ... The result should be a list of lists. ... This version uses LOOP, and it's rather short: ...
    (comp.lang.lisp)
  • re: lisp from perl
    ... (elt (elt LoL i) ... Note that in Lisp you'd probably use ... vectors rather than lists if you ... (loop for list in LoL ...
    (comp.lang.lisp)
  • Re: Cons cell archaic!?
    ... How would the implementation of a Lisp without a using cons look like? ... the irregularity in its often cited regular syntax. ... Lisp at core is based on functional programing on lists. ...
    (comp.lang.lisp)
  • Re: How powerful macros are?
    ... >> for software engineers to use arrays for everything, ... Did I miss something or is #an impossibly unbearable syntax in Lisp? ... and arrays are often slower for very short lists. ... I've also extended the language so that I have re-readable hash tables ...
    (comp.lang.lisp)