From: wildwood
Subject: Question about PG's ACL
Date: 
Message-ID: <1115141814.045240.20440@f14g2000cwb.googlegroups.com>
I'm working on the exercises for Chapter 6 of Ansi Common Lisp, and I
would like folks' opinions about question 2.  The text of the question
goes like this:

"Define a version of 'bin-search' (above) that takes :key, :test,
:start, and :end arguments with the usual meanings and defaults."

'bin-search' is, as you probably guessed, a function that takes an
object and a sorted vector, and returns the object if it finds it in
the vector.  It calls a recursive function that takes the object, the
vector, and the start and end indexes to search.

My question is, what would the "usual meanings and defaults" be for
:key and :test?  (:start and :end I can figure out...)  Is :test a
function for equality testing only, or would it be a comparator (<=>)
function?  I can't get any clear picture from the appendix of how :key
is usually used.  Unless it overrides the 'object to search for'
parameter, which doesn't make any sense.

Any advice and opinions greatly appreciated.

Thanks,
David

From: ··············@hotmail.com
Subject: Re: Question about PG's ACL
Date: 
Message-ID: <1115154319.071692.99260@o13g2000cwo.googlegroups.com>
wildwood wrote:
> I'm working on the exercises for Chapter 6 of Ansi Common Lisp, and I
> would like folks' opinions about question 2.  The text of the
question
> goes like this:
>
> "Define a version of 'bin-search' (above) that takes :key, :test,
> :start, and :end arguments with the usual meanings and defaults."
...
>
> My question is, what would the "usual meanings and defaults" be for
> :key and :test?

If you haven't discovered it yet, you should take a look at the Common
Lisp Hyperspec for issues like this:

http://www.lispworks.com/documentation/HyperSpec/

By looking in the "Master Index" under ":key," I was able to find these
sections,

http://www.lispworks.com/documentation/HyperSpec/Body/17_bb.htm
http://www.lispworks.com/documentation/HyperSpec/Body/17_ba.htm

Those seem to be very abstract, but are probably the most complete and
accurate answer to your question.

As an aside, I'm not sure why the italicized term "satisfies the test"
does not get hyperlinked, while "satisfy the test" has an entry in the
glossary.

http://www.lispworks.com/documentation/HyperSpec/Body/26_glo_s.htm#satisfy_the_test

That glossary entry, now that I look at it, also has non-linked
italicized terms.
From: Kenny Tilton
Subject: Re: Question about PG's ACL
Date: 
Message-ID: <4277C3FD.1060902@nyc.rr.com>
wildwood wrote:

> I'm working on the exercises for Chapter 6 of Ansi Common Lisp, and I
> would like folks' opinions about question 2.  The text of the question
> goes like this:
> 
> "Define a version of 'bin-search' (above) that takes :key, :test,
> :start, and :end arguments with the usual meanings and defaults."
> 
> 'bin-search' is, as you probably guessed, a function that takes an
> object and a sorted vector, and returns the object if it finds it in
> the vector.  It calls a recursive function that takes the object, the
> vector, and the start and end indexes to search.
> 
> My question is, what would the "usual meanings and defaults" be for
> :key and :test? 

key is a function applied to each candidate to return the object 
actually to be compared with the one being sought. So the default is 
IDENTITY. If you wanted to find a string of a certain length, you could 
write: (find 42 strings :key 'length).

test is the function used to compare the values. eql is the default. if 
you were searching a list of strings: (find "42" strings :test 
'string-equal)

kt

  (:start and :end I can figure out...)  Is :test a
> function for equality testing only, or would it be a comparator (<=>)
> function?  I can't get any clear picture from the appendix of how :key
> is usually used.  Unless it overrides the 'object to search for'
> parameter, which doesn't make any sense.
> 
> Any advice and opinions greatly appreciated.
> 
> Thanks,
> David
> 

-- 
Cells? Cello? Cells-Gtk?: http://www.common-lisp.net/project/cells/
Why Lisp? http://lisp.tech.coop/RtL%20Highlight%20Film

"Doctor, I wrestled with reality for forty years, and I am happy to 
state that I finally won out over it." -- Elwood P. Dowd
From: wildwood
Subject: Re: Question about PG's ACL
Date: 
Message-ID: <1115147572.314234.134850@o13g2000cwo.googlegroups.com>
Kenny Tilton wrote:
>
> key is a function applied to each candidate to return the object
> actually to be compared with the one being sought. So the default is
> IDENTITY. If you wanted to find a string of a certain length, you
could
> write: (find 42 strings :key 'length).
>
> test is the function used to compare the values. eql is the default.
if
> you were searching a list of strings: (find "42" strings :test
> 'string-equal)
>
> kt
>

Cool, thanks!  That gives me some ideas for some of the later problems
in the chapter...

--David
From: Rob Warnock
Subject: Re: Question about PG's ACL
Date: 
Message-ID: <w6Gdnd4jxLMUGOXfRVn-qw@speakeasy.net>
Kenny Tilton  <·······@nyc.rr.com> wrote:
+---------------
| wildwood wrote:
| > My question is, what would the "usual meanings and defaults" be for
| > :key and :test? 
| 
| key is a function applied to each candidate to return the object 
| actually to be compared with the one being sought. So the default is 
| IDENTITY. If you wanted to find a string of a certain length, you could 
| write: (find 42 strings :key 'length).
| 
| test is the function used to compare the values. eql is the default.
| if  you were searching a list of strings: (find "42" strings :test 
| 'string-equal)
+---------------

And if you wanted to find the first string of at *least* a certain
length, you could combine both keywords and write:

	> (let ((strings '("foo" "bar" "blather" "gorp" "bleep")))
	    (find 4 strings :key 'length :test '<= ))

        "blather"
	> 

Finally, as an example of gross abuse of the :TEST facility, I once
used the following when I was too lazy to write a tree walker:  ;-}  ;-}

	> (defun process-leaf (x y)
	    (declare (ignore y))
	    (when x
	      (format t "Leaf = ~s~%" x)) ; or some more complex processing
	    t)

	PROCESS-LEAF
	> (let ((tree '(a b (c ((d e) f) g (h . i) j))))
	    (tree-equal tree tree :test #'process-leaf))
	Leaf = A
	Leaf = B
	Leaf = C
	Leaf = D
	Leaf = E
	Leaf = F
	Leaf = G
	Leaf = H
	Leaf = I
	Leaf = J
	T
	> 


-Rob

-----
Rob Warnock			<····@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607
From: Luis Oliveira
Subject: Re: Question about PG's ACL
Date: 
Message-ID: <m24qdiifi7.fsf@pomajxego.local>
Kenny Tilton <·······@nyc.rr.com> writes:

> wildwood wrote:
>> "Define a version of 'bin-search' (above) that takes :key, :test,
>> :start, and :end arguments with the usual meanings and defaults."

> test is the function used to compare the values. eql is the
> default. if you were searching a list of strings: (find "42" strings
> :test 'string-equal)

How do you implement binary search with EQL?
From: Kenny Tilton
Subject: Re: Question about PG's ACL
Date: 
Message-ID: <w7pee.17150$mp6.3396784@twister.nyc.rr.com>
Luis Oliveira wrote:

> Kenny Tilton <·······@nyc.rr.com> writes:
> 
> 
>>wildwood wrote:
>>
>>>"Define a version of 'bin-search' (above) that takes :key, :test,
>>>:start, and :end arguments with the usual meanings and defaults."
> 
> 
>>test is the function used to compare the values. eql is the
>>default. if you were searching a list of strings: (find "42" strings
>>:test 'string-equal)
> 
> 
> How do you implement binary search with EQL?

Hunh? The OP is a Lisp newby who just wanted to know the traditional 
roles of KEY and TEST. I answered in the context of FIND.

kenny

-- 
Cells? Cello? Cells-Gtk?: http://www.common-lisp.net/project/cells/
Why Lisp? http://lisp.tech.coop/RtL%20Highlight%20Film

"Doctor, I wrestled with reality for forty years, and I am happy to 
state that I finally won out over it." -- Elwood P. Dowd