Changes between Version 65 and Version 66 of HashTablesCowan


Ignore:
Timestamp:
06/15/13 14:57:40 (4 years ago)
Author:
cowan
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • HashTablesCowan

    v65 v66  
    1717== Issues == 
    1818 
    19  1. Should we support [wiki:ComparatorsCowan comparators] as alternatives to equality procedures?  That packages up the equality predicate with the hash function; if no hash function is available, but an order predicate is, the hash table can fall back to an O(log n) tree. 
    20  
    21  2. Alternatively, what if we did not support arbitrary equality predicates, but only allowed `eq?`, `eqv?`, `equal?`, and `string=?` (hash tables that support `equal?` will also support `string=?`).  We could further allow `string-ci=?` as an optional ("should") equality predicate.  This would allow us to support more Scheme implementations and eliminate any need to deal with user-specified hash functions, though it is a considerable restriction on generality. 
     19 1. (resolved) 
     20 
     21 2. (resolved) 
    2222 
    2323== Rationale == 
     
    2727There is no mandated support for thread safety, immutability, or weakness, though there is a semi-portable hook for specifying these features. 
    2828 
     29This specification accepts separate equality predicates and hash functions for backward compatibility, but strongly encourages the use of [http://srfi.schemers.org/srfi-114/srfi-114.html SRFI 114] comparators, which package a type test, an equality predicate, and a hash function into a single bundle. 
     30 
    2931 
    3032=== SRFI 69 compatibility === 
     
    128130=== Constructors === 
    129131 
    130 `(make-hash-table `''equality'' [ ''hash'' ] [ ''arg'' ... ]`)` 
    131  
    132 Returns a newly allocated hash table whose equality predicate is ''equality'' and hash function is ''hash''.  The equality predicate accepts two arguments and returns a truth value.  The hash function accepts one argument in the domain of the equality predicate and returns a non-negative exact integer.  It is the programmer's responsibility to ensure that two objects passed to the hash function return the same value if the same objects passed to the equality predicate return true; however, the converse is not required. 
    133  
    134 The ability to omit the ''hash'' argument is severely limited.  If ''equality'' is `eq?`, `eqv?`, `equal?`, `string=?`, or `string-ci=?`, then if ''hash'' is not provided, a suitable implementation-provided procedure will be used; the implementation may use its own procedure in any case.  The implementation may extend this list.  But if any other equality predicate is provided without a hash function, an error should be signaled. 
     132`(make-hash-table `''comparator'' [ ''hash'' ] [ ''arg'' ... ]`)` 
     133 
     134Returns a newly allocated hash table whose equality predicate and hash function are extracted from ''comparator''.  If the argument is a procedure instead, it is assumed to be the equality predicate, and the hash function is ''hash''.  The equality predicate accepts two arguments and returns a truth value.  The hash function accepts one argument in the domain of the equality predicate and returns a non-negative exact integer.  It is the programmer's responsibility to ensure that two objects passed to the hash function return the same value if the same objects passed to the equality predicate return true; however, the converse is not required. 
     135 
     136If a bare equality predicate rather than a comparator is provided, the ability to omit the ''hash'' argument is severely limited.  If ''equality'' is `eq?`, `eqv?`, `equal?`, `string=?`, or `string-ci=?`, then the implementation must provide a hash function, which it may use in any case.  The implementation may extend this list.  But if any other equality predicate is provided without a hash function, an error should be signaled. 
    135137 
    136138The meaning of the remaining arguments is implementation-dependent.  However, implementations which support the ability to specify the initial capacity of a hash table should interpret a non-negative exact integer as the specification of that capacity.  In addition, if the symbols `immutable`, `thread-safe`, `weak-keys` or  `weak-values` are present, implementations should create immutable hash tables, mutable thread-safe hash tables, hash tables with weak keys, and hash tables with weak values respectively.  In an implementation which does not support these features, an error should be signaled if they are requested.  To avoid collision with the ''hash'' argument, none of these arguments can be procedures. 
     
    138140(SRFI 69 `make-hash-table`; R6RS `make-eq-hashtable`, `make-eqv-hashtable`, and `make-hashtable`; Common Lisp `make-hash-table`) 
    139141 
    140 `(hash-table `''equality hash'' ( ''key value'' ) ...`)` 
    141  
    142 Returns a newly allocated hash table, created as if by `make-hash-table`, whose equality procedure is `equality` and hash function is `hash`.  For each pair of arguments, an association is added to the new hash table with ''key'' as its key and ''value'' as its value. 
    143  
    144 `(hash-table-unfold `''continue? mapper successor seed equality'' [ ''hash'' ]`)` 
     142`(hash-table `''comparator'' ( ''key value'' ) ...`)` 
     143 
     144Returns a newly allocated hash table, created as if by `make-hash-table`.  For each pair of arguments, an association is added to the new hash table with ''key'' as its key and ''value'' as its value. 
     145 
     146`(hash-table-unfold `''continue? mapper successor seed comparator'' [ ''hash'' ]`)` 
    145147 
    146148Create a new hash table as if by `make-hash-table`.  If the result of applying the predicate ''continue?'' to ''seed'' is `#f`, return the hash table.  Otherwise, apply the procedure ''mapper'' to ''seed''.  ''Mapper'' returns two values, which are inserted into the hash table as the key and the value respectively.  Then get a new seed by applying the procedure ''successor'' to ''seed'', and repeat this algorithm. 
     
    158160`(hash-table=? `''value= hash-table,,1,, hash-table,,2,,''`)` 
    159161 
    160 Returns `#t` if ''hash-table,,1,,'' and ''hash-table,,2,,'' have the same size, the same keys (in the sense of their common equality predicate) and the same values (in the sense of the ''value='' predicate) for each key, and `#f` otherwise.  It is an error to compare two hash tables that have distinct equality predicates. 
     162Returns `#t` if ''hash-table,,1,,'' and ''hash-table,,2,,'' have the same size, the same keys (in the sense of their common equality predicate) and the same values (in the sense of the ''value='' predicate) for each key, and `#f` otherwise.  It is an error to compare two hash tables that have distinct comparators or distinct equality predicates. 
    161163 
    162164=== Accessors === 
     
    181183`(hash-table-set! `''hash-table key value''`)` 
    182184 
    183 Creates a new association in ''hash-table'' that associates ''key'' with ''value''.  If there is a previous association for ''key'', it is deleted.  It is an error if ''key'' is not a valid argument to the equality predicate of ''hash-table''.  Returns an unspecified value.  Must execute in expected amortized constant time.  (SRFI 69 `hash-table-set!`; R6RS `hashtable-set!`) 
     185Creates a new association in ''hash-table'' that associates ''key'' with ''value''.  If there is a previous association for ''key'', it is deleted.  It is an error if the type check procedure of the comparator of ''hash-table'', when invoked on ''key'', does not return `#t`. Likewise, it is an error if ''key'' is not a valid argument to the equality predicate of ''hash-table''.  Returns an unspecified value.  Must execute in expected amortized constant time.  (SRFI 69 `hash-table-set!`; R6RS `hashtable-set!`) 
    184186 
    185187`(hash-table-set-all! `''hash-table'' ( ''key value'' ) ...`)` 
     
    290292These procedures process the associations of the hash table in arbitrary order. 
    291293 
    292 `(hash-table-map `''equality hash proc merger hash-table''`)` 
     294`(hash-table-map `''comparator proc merger hash-table''`)` 
    293295 
    294296Returns a newly allocated hash table as if by `make-hash-table`.  Calls ''proc'' for every association in ''hash-table'' with two arguments: the key of the association and the value of the association.  The two values returned by ''proc'' are inserted into the new hash table as a key and value. 
     
    322324Returns an alist with the same associations as ''hash-table'' in an unspecified order. 
    323325 
    324 `(alist->hash-table `''alist equality hash''`)` 
     326`(alist->hash-table `''alist comparator hash''`)` 
    325327 
    326328Returns a newly allocated hash-table as if by `make-hash-table`, initializing it from the associations of ''alist''.  (SRFI 69 `alist->hash-table`)