Subject: Re: searching by a key in a sub-sub-list without iteration?
From: rpw3@rpw3.org (Rob Warnock)
Date: Fri, 27 Oct 2006 02:20:06 -0500
Newsgroups: comp.lang.scheme,comp.lang.lisp
Message-ID: <6K-dnaPkL6a7LtzYnZ2dnUVZ_oKdnZ2d@speakeasy.net>
Mad Scientist Jr <usenet_daughter@yahoo.com> wrote:
+---------------
| But is there some way to retrieve the sub-sub-list without knowing the
| sub-list's key, and without having to iterate through all the sublists,
| like: (RetrieveSubSubList "grasshopper")
+---------------

No, but the CL functions TREE-EQUAL (given an appropriate :TEST arg)
or SUBST-IF can be perverted into serving as a tree walker for you.

But just writing a simple one for yourself is easier, and will
help you a lot in learning the language. This one took me barely
five minutes to code and test [and only 7 lines of code, 10 if
you include the doc string]:

    > (describe #'tree-assoc)

    #<Function TREE-ASSOC {58A0D1F9}> is function.
    Arguments:
      (tag tree &key (test #'eql) (key #'identity))
    Function documentation:
      Do a left-to-right depth-first walk of TREE and return the first
      cons in TREE whose car (as transformed by the KEY) satisfies the 
      TEST when compared with ITEM, or NIL if no such cons is found.
    Its defined argument types are:
      (T T &KEY (:TEST T) (:KEY T))
    Its result type is:
      *
    On Thursday, 10/26/06 11:50:42 pm PDT it was compiled from:
    #(#'(LAMBDA # #))

    > (tree-assoc "Grasshopper" mylist) 

    NIL
    > (tree-assoc "Grasshopper" mylist :test #'equal)

    NIL
    > (tree-assoc "Grasshopper" mylist :test #'equalp)

    ("grasshopper"
     (("description" "contains lots of protein") ("price" 0.1)
      ("color" "green")))
    > 

Yes, I deliberately captialized "Grasshopper", to make it a
better example of :TEST arguments in traversal functions.


-Rob

p.s. Do be sure to implement the :KEY convention in your version
of TREE-ASSOC, too, because that lets you do fun stuff like this:

    > (flet ((my-key (x)
	      (format t "Looking at ~S~%" x)
	      x))
	(tree-assoc "Grasshopper" mylist :test #'equalp :key #'my-key))
    Looking at "animal"
    Looking at "panda"
    Looking at "description"
    Looking at "big news when they give birth"
    Looking at "price"
    Looking at 75000
    Looking at "color"
    Looking at "black and white"
    Looking at "lion"
    Looking at "description"
    Looking at "very dangerous"
    Looking at "price"
    Looking at 50000
    Looking at "color"
    Looking at "golden"
    Looking at "grasshopper"
    ("grasshopper"
     (("description" "contains lots of protein") ("price" 0.1)
      ("color" "green")))
    > 

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607