Difference between revisions of "Chained Dictionary Assignment"
Line 103: | Line 103: | ||
One can imagine the utility of having a simple Dictionary without the overhead of a HashTable. Perhaps, the number of anticipated entries is small. Perhaps, its performance is not critical. Maybe the client has a lot of tasks on his or her plate and simply does not feel like creating a custom hash function for their type. Whatever the reason, it seems like a reasonable implementation of Dictionary to provide. | One can imagine the utility of having a simple Dictionary without the overhead of a HashTable. Perhaps, the number of anticipated entries is small. Perhaps, its performance is not critical. Maybe the client has a lot of tasks on his or her plate and simply does not feel like creating a custom hash function for their type. Whatever the reason, it seems like a reasonable implementation of Dictionary to provide. | ||
− | === | + | We |
+ | |||
+ | <nowiki>structure SingleChainedDictionary = DictionaryFn(struct | ||
+ | |||
+ | (* TODO: replace unit with the type you decide upon *) | ||
+ | type (''k,'v) dictionary = unit | ||
+ | |||
+ | type ''k create_parameter_type = unit | ||
+ | |||
+ | fun create() : (''k,'v) dictionary = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | |||
+ | fun get(dict : (''k,'v) dictionary, key : ''k) : 'v option = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | |||
+ | fun put(dict : (''k,'v) dictionary, key : ''k , value : 'v) : (''k,'v) dictionary * 'v option = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | |||
+ | fun remove(dict : (''k,'v) dictionary, key : ''k) : (''k,'v) dictionary * 'v option = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | |||
+ | fun entries(dict : (''k,'v) dictionary) : (''k*'v) list = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | |||
+ | end)</nowiki> | ||
+ | |||
+ | =type (''k,'v) dictionary= | ||
Change the definition of <code>type (''k,'v) dictionary</code> to support SingleChainedDictionary. | Change the definition of <code>type (''k,'v) dictionary</code> to support SingleChainedDictionary. | ||
Line 111: | Line 137: | ||
end</nowiki> | end</nowiki> | ||
− | + | === entries === | |
+ | Define the entries method so we can take advantage of the <code>keys</code> and <code>values</code> functions you implemented on <code>functor HasEntriesFn</code>. | ||
− | + | <nowiki>fun entries(dict : (''k,'v) dictionary) : (''k*'v) list = | |
− | <nowiki> | + | raise Fail "NotYetImplemented"</nowiki> |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
=== structure SingleChainHasChaining === | === structure SingleChainHasChaining === |
Revision as of 21:09, 11 October 2022
Contents
Motivation
In this and the follow up Sorted Dictionary studio, you will build three implementations of a dictionary. Each will be a persistent, mutable data structure, so you can expect to use the ref feature of SML, either directly or via the mutable Array structure.
Background
SML structure Vector
tabulate : int * (int -> 'a) -> 'a vector
length : 'a vector -> int
sub : a vector * int -> 'a
update : 'a vector * int * 'a -> 'a vector
foldl : ('a * 'b -> 'b) -> 'b -> 'a vector -> 'b
SML structure Option
datatype 'a option = NONE | SOME of 'a
HashTable
Code To Investigate
signature Dictionary
Note the include in the DICTIONARY signature.
signature DICTIONARY_FUNCTOR_PARAMETER = sig type (''k,'v) dictionary type ''k create_parameter_type val create : ''k create_parameter_type -> (''k,'v) dictionary val get : ((''k,'v) dictionary *''k) -> 'v option val put : ((''k,'v) dictionary *''k *'v) -> (''k,'v) dictionary * 'v option val remove : ((''k,'v) dictionary *''k) -> (''k,'v) dictionary * 'v option val entries : (''k,'v) dictionary -> (''k*'v) list end signature DICTIONARY = sig include DICTIONARY_FUNCTOR_PARAMETER val keys : (''k,'v) dictionary -> ''k list val values : (''k,'v) dictionary -> 'v list end
create
Specific to each structure. Creates an empty immutable Dictionary.
get
Behaves much like java.util.Map<K,V>'s get(key) method except instead of returning null or the associated value, it returns an option.
put
Behaves much like java.util.Map<K,V>'s put(key,value) method except
- instead of mutating the provided dictionary, it returns an immutable updated dictionary.
- instead of returning null or the previously associated value, it returns an option of the associate value (along with the updated dictionary in a 2-tuple).
remove
Behaves much like java.util.Map<K,V>'s remove(key) method except instead of returning null or the previously associated value, it returns an option.
- instead of mutating the provided dictionary, it returns an immutable updated dictionary.
- instead of returning null or the previously associated value, it returns an option of the associate value (along with the updated dictionary in a 2-tuple).
entries
Behaves much like java.util.Map<K,V>'s entrySet() method.
keys
Behaves much like java.util.Map<K,V>'s keySet() method.
values
Behaves much like java.util.Map<K,V>'s values() method.
Code To Implement
functor DictionaryFn
Each implementation of dictionary can reuse the same functions which given a list of entries produce the keys and values. functor DictionaryFn
accepts a signature parameter which defines all of the necessary functions besides keys
and values
. Critically, this includes the entries
function which can be employed to support the keys
and values
functions.
keys
One of List's higher order functions can be useful here. Which one is it?
fun keys(dict : (''k,'v) dictionary) : ''k list = raise Fail "NotYetImplemented"
values
One of List's higher-order functions can be useful here. Which one is it?
fun values(dict : (''k,'v) dictionary) : 'v list = raise Fail "NotYetImplemented"
structure Chain
Both the SingleChainedDictionary and the HashedDictionary will leverage chaining to deal with collisions. A collision is where more than one (key, value) entry wants to be store in the same chain (a.k.a. list of (key, value) entries). For the SingleChainedDictionary, every unique key will "collide" with every other one since all of them will be stored in the single chain of the SingleChainedDictionary. For the HashedDictionary, there should be fewer collisions since there will be a multiple chains to spread the load, but handling collisions should be similar to the SingleChainedDictionary once the appropriate chain is determined.
We implement structure Chain so we can use the code in both SingleChainedDictionary and HashedDictionary.
signature CHAIN = sig val get : (''k*'v) list * ''k -> 'v option val put : (''k*'v) list * ''k * 'v -> ((''k*'v) list * 'v option) val remove : (''k*'v) list * ''k -> ((''k*'v) list * 'v option) end
get
fun get(chain : (''k*'v) list, key:''k) : 'v option = raise Fail "NotYetImplemented"
put
fun put(chain : (''k*'v) list, key:''k, value:'v) : (''k*'v) list * 'v option = raise Fail "NotYetImplemented"
remove
fun remove(chain : (''k*'v) list, key : ''k) : (''k*'v) list * 'v option = raise Fail "NotYetImplemented"
structure SingleChainedDictionary
One can imagine the utility of having a simple Dictionary without the overhead of a HashTable. Perhaps, the number of anticipated entries is small. Perhaps, its performance is not critical. Maybe the client has a lot of tasks on his or her plate and simply does not feel like creating a custom hash function for their type. Whatever the reason, it seems like a reasonable implementation of Dictionary to provide.
We
structure SingleChainedDictionary = DictionaryFn(struct (* TODO: replace unit with the type you decide upon *) type (''k,'v) dictionary = unit type ''k create_parameter_type = unit fun create() : (''k,'v) dictionary = raise Fail "NotYetImplemented" fun get(dict : (''k,'v) dictionary, key : ''k) : 'v option = raise Fail "NotYetImplemented" fun put(dict : (''k,'v) dictionary, key : ''k , value : 'v) : (''k,'v) dictionary * 'v option = raise Fail "NotYetImplemented" fun remove(dict : (''k,'v) dictionary, key : ''k) : (''k,'v) dictionary * 'v option = raise Fail "NotYetImplemented" fun entries(dict : (''k,'v) dictionary) : (''k*'v) list = raise Fail "NotYetImplemented" end)
type (k,'v) dictionary
Change the definition of type (k,'v) dictionary
to support SingleChainedDictionary.
structure TypeHolder = struct (* TODO: replace unit with the type you decide upon *) type (''k,'v) dictionary = unit end
entries
Define the entries method so we can take advantage of the keys
and values
functions you implemented on functor HasEntriesFn
.
fun entries(dict : (''k,'v) dictionary) : (''k*'v) list = raise Fail "NotYetImplemented"
structure SingleChainHasChaining
The two functions getChainOfEntriesForKey(dict, key)
and setChainOfEntriesForKey(dict, key, nextEntries)
used to parameterize functor>HasChainingFn
are passed a key parameter. Since the chain will be the same for all keys, SingleChainedDictionary can ignore this key parameter (unlike HashedDictionary which will return different chains for different keys).
structure SingleChainHasChaining = HasChainingFn (struct type (''k,'v) dictionary = (''k,'v) TypeHolder.dictionary fun getChainOfAllEntries(dict : (''k,'v) dictionary) : (''k*'v) list = raise Fail "NotYetImplemented" fun setChainOfAllEntries(dict : (''k,'v) dictionary, nextEntries : (''k*'v) list) : unit = raise Fail "NotYetImplemented" fun getChainOfEntriesForKey(dict : (''k,'v) dictionary, key : ''k) : (''k*'v) list = getChainOfAllEntries(dict) fun setChainOfEntriesForKey(dict : (''k,'v) dictionary, key : ''k, nextEntries : (''k*'v) list) : unit = setChainOfAllEntries(dict, nextEntries) end)
getChainOfAllEntries
Note: this function is called from getChainOfEntriesForKey, dropping the unnecessary key paremeter.
setChainOfAllEntries
Note: this function is called from setChainOfEntriesForKey, dropping the unnecessary key paremeter.
create function
fun create() : (''k,'v) dictionary = raise Fail "NotYetImplemented"
structure HashedDictionary
signature HASHED_DICTIONARY
We can see that signature HASHED_DICTIONARY
includes DICTIONARY
and adds a create
function which accepts the number of buckets to create along with a hash function.
structure HashedDictionary :> HASHED_DICTIONARY
signature HASHED_DICTIONARY = sig include DICTIONARY type ''k hash_function = ''k -> int val create : (int * ''k hash_function) -> (''k,'v) dictionary end
structure TypeHolder
Change the definition of type (k,'v) dictionary
to support HashedDictionary.
structure TypeHolder = struct (* TODO: replace unit with the type you decide upon *) type (''k,'v) dictionary = unit end
structure HashedHasEntries
structure HashedHasEntries = HasEntriesFn (struct type (''k,'v) dictionary = (''k,'v) TypeHolder.dictionary fun entries(dict : (''k,'v) dictionary) : (''k*'v) list = raise Fail "NotYetImplemented" end)
entries
Define the entries method so we can take advantage of the keys
and values
functions you implemented on functor HasEntriesFn
.
structure HashedHasChaining
structure HashedHasChaining = HasChainingFn (struct type (''k,'v) dictionary = (''k,'v) TypeHolder.dictionary fun positive_remainder(v : int, n : int) : int = let val result = v mod n in if result >= 0 then result else result+n end fun getChainOfEntriesForKey(dict : (''k,'v) dictionary, key : ''k) : (''k*'v) list = raise Fail "NotYetImplemented" fun setChainOfEntriesForKey(dict : (''k,'v) dictionary, key : ''k, nextEntries : (''k*'v) list) : unit = raise Fail "NotYetImplemented" end)
getChainOfEntriesForKey
setChainOfEntriesForKey
create function
fun create(bucket_count_request : int, hash : ''k hash_function) : (''k,'v) dictionary = raise Fail "NotYetImplemented"
Testing
source folder: | src/test/sml/dictionary/chained |
how to run with CM.make verbosity off: | sml -Ccm.verbose=false run_chained_testing.sml |
how to run with CM.make verbosity on: | sml run_chained_testing.sml |
note: ensure that you have removed all printing to receive credit for any assignment.
Pledge, Acknowledgments, Citations
file: | exercise-chained-dictionary-pledge-acknowledgments-citations.txt |
More info about the Honor Pledge