[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Interface view of dictionaries



Lets examine your proposed API for dictionaries, and contrast it with 
SRFI-44.

On Sat, Oct 25, 2003 at 12:27:54PM -0700, bear wrote:
> (create-*) 
(make-*)

> (*-insert! dict datum key),
*-put dictionary key value

> 
>      ;; fetch is a key lookup.
> (*-fetch dict key),
*-get dict key

> (*-fetch-deleting! dict key)
[A]
(define (*-fetch-deleting! dict key)
  (let ([rv (*-get dict key)])
    (*-remove! dict key)
    rv))

Additionally, fetch-deleting! does not map to many dictionaries, for 
example disk file database, *without* doing the above.

> 
>      ;; get just gets one or more elements without caring which.
> (*-get-one dict)
(*-get-left dict)

> (*-get-one-deleting! dict)
As in [A], with the same caveats.

> (*-get-n dict num)
> (*-get-n-deleting! dict num)
Trivially defined with enumeration.
 
>      ;; the following two are for functions of the signature
>      ;; (callback dict keyval dataval)
> (*-foreach dict callback)
> (*-foreach! dict callback)
(collection-fold-left dict fold-function)
;; a copy is made of the dict to protect it from side effects
Are you generating a new collection?  Then *-map is the name you want.  
for-each implies iteration over values (which is what the enumerators 
are for).  

>      ;; side effects happen to the dictionary.
> 
> (*-size dict) ;; returns number of datum/key pairs stored
The same.

> (get-iterator dict)   ;; returns an iterator function that
>                       ;; takes a key arg and returns some "next" key,
>                       ;; or takes '() and returns some (arbitrarily
>                       ;; chosen for unordered dictionaries) "first" key.
> 
> (*-nextkey dict) ;; same as function returned from get-iterator
> (*-nextkey dict key) ;; same as returned from the get-iterator func above
> (*-lastkey dict)     ;; same as returned from the get-reversed-iterator func
> (get-reversed-iterator dict)

See Olegs post on the hazards of iterators.

> 
> ;; the following is a test to see whether the "Ordered dictionary"
> ;; interface is also provided. The test for ordered dictionaries could
> ;; be part of the interface for all dictionaries.
> 
> (ordered-dict? dict)
(ordered-collection? dict)

<snip>Efficiency procs
Best left to a separate SRFI.
> 
> Some dictionaries would also provide the "ordered dictionary"
> interface -- which includes
> 
> (create-* <key ordering function>)
(make-* ordering-function)
> (*-fetchfirst dict)  ;; returns 1 entry
(*-get-left dict)

> (*-fetchfirst dict number) ;; returns number entries
[B] Trivially implemented with collection-fold-left

> (*-fetchfirst-deleting! dict)
> (*-fetchfirst-deleting! dict number)
See [A]

> (*-fetchlast dict)
(*-get-right dict)
> (*-fetchlast dict number)
See [B]

> (*-fetchlast-deleting! dict)
> (*-fetchlast-deleting! dict number)
See [A]

> (*-fetchrange dict key1 key2)
Possibly novel, but also implementable with enumeration

> (*-fetch-next-n dict key1 number)
> (*-fetch-next-n-deleting! dict key1 number)
> (*-fetch-prev-n dict key1 number)
> (*-fetch-prev-n-deleting! dict key1 number)
> (*-fetchrange-deleting! dict key1 key2)
Above + [A]

> (*-firstkey dict)
One step in enumeration

> 
> (dictionary? htable) => #t
> (dictionary? pqueue) => #t
> (dictionary? btree) => #t
> (dictionary? olist) => #t
> (dictionary? alyst) => #t
Already exists.

> 
> (ordered-dict? htable) => #f
> (ordered-dict? alyst) => #f
> (ordered-dict? olist) => #t
> (ordered-dict? btree) => #t
> (ordered-dict? pqueue) => #t
(and (dictionary? coll) (ordered-collection? coll))

So, you see, your API is almost *exactly* like the current SRFI apart 
from minor naming variations.  Where it differs, there has been strong 
refutation for that approach.  I must ask, did you *read* the SRFI 
carefully?

	Scott

Attachment: pgpfMK6fIOCI3.pgp
Description: PGP signature