Newbie question : Linked-list replacement 
Author Message
 Newbie question : Linked-list replacement

Hi all
        I just started learning lisp last week and so-far so-good. One
hurdle I've come up against is storage of structures. Normally, say I
was receiving user input and storing the results in a series of
identical structures I'd pop them into a linked list. However, I'm sure
there must be a better way in lisp. At first I was thinking I could just
put them into a simple list. This would however require dynamically
creating a label for each structure as I instanced it as I am assuming I
don't know how many structures I will have. Ideally I would create the
label from content info somehow  and I have no Idea how to solve the
problem.

        Any relies gratefully received, yes I know i'm clueless.

                                thanks

                                        Andrew

--

===========================
      Andrew  Lawson

===========================



Mon, 11 Aug 2003 18:11:11 GMT  
 Newbie question : Linked-list replacement

Quote:

> Hi all
>    I just started learning lisp last week and so-far so-good. One
> hurdle I've come up against is storage of structures. Normally, say I
> was receiving user input and storing the results in a series of
> identical structures I'd pop them into a linked list. However, I'm sure
> there must be a better way in lisp. At first I was thinking I could just
> put them into a simple list. This would however require dynamically
> creating a label for each structure as I instanced it as I am assuming I
> don't know how many structures I will have. Ideally I would create the
> label from content info somehow  and I have no Idea how to solve the
> problem.

        You may be better off using a hash table; this gives you
efficient lookup of records based on a key.

        Assuming that the records have a unique id field, you can use
this field as the hash table key (note: depending on the type of the
id field, you may have to specify #'equal or #'equalp as the hash
table test instead of the default #'eql).

        See the Common Lisp HyperSpec for details on make-hash-table
and gethash, if you're not familar with these.

        http://www.xanalys.com/software_tools/reference/HyperSpec/

--
Raymond Wiker



Mon, 11 Aug 2003 18:29:14 GMT  
 Newbie question : Linked-list replacement

Quote:

> Hi all
>    I just started learning lisp last week and so-far so-good. One
> hurdle I've come up against is storage of structures. Normally, say I
> was receiving user input and storing the results in a series of
> identical structures I'd pop them into a linked list. However, I'm sure
> there must be a better way in lisp. At first I was thinking I could just
> put them into a simple list. This would however require dynamically
> creating a label for each structure as I instanced it as I am assuming I
> don't know how many structures I will have. Ideally I would create the
> label from content info somehow  and I have no Idea how to solve the
> problem.

I have to admit I do not understand fully what you problem is. So I
think you ask how to store structures somehere. Now here's one way
doing it:

(defstruct (point
            (:print-function
             (lambda (struct stream depth)
               (declare (ignore depth))
               (format stream "x = ~A, y= ~A~%"
                       (point-x-coord struct)
                       (point-y-coord struct)))))
  (x-coord 0.0 :type float)
  (y-coord 0.0 :type float))

(defun translate (pt dx dy)
  "Move point by dx into x-direction and dy in y-direction"
  (setf (point-x-coord pt) (+ (point-x-coord pt) dx))
  (setf (point-y-coord pt) (+ (point-y-coord pt) dy))
  (values))

(defun main ()
  (let ((list '())
        (p1 (make-point :x-coord 10.0
                        :y-coord 10.0))
        (p2 (make-point :x-coord 20.0
                        :y-coord 20.0)))
        (push p1 list)
        (push p2 list)

        (setf list (map 'list #'(lambda (pt) (translate pt 10.0 5.0) pt)
                        (nreverse list)))
        (dolist (item  list) (princ item))
        (values)))

you can just add Structures as you like to Lists and if you do not
like what I did with p1 and p2 just use
(push (make-point :x-coord 10.0
                  :y-coord 10.0) list)

Or the like.

I hope this helps a bit

Friedrich



Mon, 11 Aug 2003 20:51:38 GMT  
 Newbie question : Linked-list replacement

Quote:

> hurdle I've come up against is storage of structures. Normally, say
> I was receiving user input and storing the results in a series of
> identical structures I'd pop them into a linked list.

If you need to `find' a particular structure in that list (or whatever
it is that you end up using), then lists are pretty good.  CL even has
a FIND function that returns the element of a sequence, and also a
similar FIND-IF function.

However, if you can attribute a unique identifier (key) to each of
those structs, then you may consider using a hashtable (see
`make-hash-table' and `gethash').

good luck,
dave



Tue, 12 Aug 2003 04:42:52 GMT  
 Newbie question : Linked-list replacement

Quote:

> Hi all
>    I just started learning lisp last week and so-far so-good. One
> hurdle I've come up against is storage of structures. Normally, say I
> was receiving user input and storing the results in a series of
> identical structures I'd pop them into a linked list. However, I'm sure
> there must be a better way in lisp. At first I was thinking I could just
> put them into a simple list. This would however require dynamically
> creating a label for each structure as I instanced it as I am assuming I
> don't know how many structures I will have. Ideally I would create the
> label from content info somehow  and I have no Idea how to solve the
> problem.

The killer question: What is there about each of those "structures"
that actually ought to be identifiable as being unique?

If the answer to that is "nothing," then pushing them onto a list
would seem perfectly acceptable.

If the answer to that is "they're ordered from first to last," then,
again, pushing them onto a list would seem perfectly acceptable.

On the other hand, if you know there are to be five of them, and that
the range (0 1 2 3 4) or (1 2 3 4 5) are reasonable to represent the
locations, then perhaps you should do:

(defparameter whole-thing (make-array 5))
  and then do things like:
(setf (aref whole-thing 2) some-complex-structure-for-pos-2)
  to assign individual values.

Yet another limb might be useful if "they're named based on a string
value."

(defparameter *whole-thing* (make-hash-table))

;;; You've pushed all the elements in the list onto the list
;;; *list-of-objects* and have a function (get-name) which extracts
;;; the name from the list.

(dolist
    (obj *list-of-objects*)
  (setf (gethash *whole-thing* (get-name obj))
        obj))

(setf *list-of-objects* NIL)

That would walk through a list of elements, push them into a hash
table keyed on whatever name GET-NAME accesses, and then blows away
the original list (since it's no longer terribly needed).

Long and short is that I suspect you're trying to solve a nonexistent
problem.  

- If there is some crucial ordering of the objects, and random access
  is needed, then you may want to walk through the list and transform
  it into a vector/array.  That might happen while constructing the
  set, or you might push a bunch of items into a list, and turn the
  list into a vector at the end.

- If random access is valuable, but order is irrelevant, a hash table
  may be the answer.

- If the elements will be accessed in order, then keeping them in a
  list seems AOK.

Those seem to be the most likely scenarios.  Other options would
include building some form of search tree, which gets complex pretty
quickly, and maybe ludicrously unvaluable.
--

http://vip.hex.net/~cbbrowne/lisp.html
Rules of the Evil Overlord #155. "If I know of any heroes in the land,
I will not under any circumstance kill their mentors, teachers, and/or
best friends."  <http://www.eviloverlord.com/>



Tue, 12 Aug 2003 11:39:48 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. Newbie question about generic linked list tasks

2. Deallocating linked lists of linked lists

3. Newbie Question, list = list + x VS append (x)

4. Ada newbie: GNAT linking error question

5. GNAT link newbie question

6. Linking in Fujitsu : Newbie Question

7. newbie question about linking ?

8. F90 linked list question

9. A basic question about linked list

10. elementary linked list question

11. Questions on linked lists

12. Newbie link problem: won't link clearly defined symbols

 

 
Powered by phpBB® Forum Software