Difference between revisions of "Chained Dictionary Assignment"
(→Vector) |
|||
Line 5: | Line 5: | ||
===Vector=== | ===Vector=== | ||
[https://smlfamily.github.io/Basis/vector.html SML Vector structure] | [https://smlfamily.github.io/Basis/vector.html SML Vector structure] | ||
+ | : [https://smlfamily.github.io/Basis/vector.html#SIG:VECTOR.tabulate:VAL tabulate] : int * (int -> 'a) -> 'a vector | ||
+ | : [https://smlfamily.github.io/Basis/vector.html#SIG:VECTOR.length:VAL length] : 'a vector -> int | ||
+ | : [https://smlfamily.github.io/Basis/vector.html#SIG:VECTOR.sub:VAL sub] : a vector * int -> 'a | ||
+ | : [https://smlfamily.github.io/Basis/vector.html#SIG:VECTOR.update:VAL update] : 'a vector * int * 'a -> 'a vector | ||
+ | : [https://smlfamily.github.io/Basis/vector.html#SIG:VECTOR.foldl:VAL foldl] : ('a * 'b -> 'b) -> 'b -> 'a vector -> 'b | ||
==HashTable== | ==HashTable== |
Revision as of 03:27, 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
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
HashTable
Code To Investigate
signature Dictionary
signature DICTIONARY = sig type (''k,'v) dictionary val get : ((''k,'v) dictionary *''k) -> 'v option val put : ((''k,'v) dictionary *''k *'v) -> 'v option val remove : ((''k,'v) dictionary *''k) -> 'v option val entries : (''k,'v) dictionary -> (''k*'v) list val keys : (''k,'v) dictionary -> ''k list val values : (''k,'v) dictionary -> 'v list end
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 returning null or the previously associated value, it returns an option.
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.
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 HasEntriesFn
Each implementation of dictionary can reuse the same functions which given a list of entries produce the keys and values. functor HasEntriesFn
accepts a signature parameter which defines an entries function to support keys
and values
functions.
functor HasEntriesFn (HasEntriesParameter : sig type (''k,'v) dictionary val entries : (''k,'v) dictionary -> (''k*'v) list end) : HAS_ENTRIES = struct
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"
functor HasChainingFn
One can anticipate that separate structures for SingleChainedDictionary
and HashedDictionary
have potential for code resuse. By parameterizing functor HasChainingFn
with getChainOfEntriesForKey
and setChainOfEntriesForKey
we can implement get
, put
, and remove
.
functor HasChainingFn (HasChainingParameter : sig type (''k,'v) dictionary val getChainOfEntriesForKey : ((''k,'v) dictionary * ''k) -> (''k*'v) list val setChainOfEntriesForKey : ((''k,'v) dictionary * ''k * (''k*'v) list) -> unit end) : HAS_CHAINING = struct
get
put
remove
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.
signature SINGLE_CHAINED_DICTIONARY
We can see that signature SINGLE_CHAINED_DICTIONARY
includes DICTIONARY
and adds a create
function.
structure SingleChainedDictionary :> SINGLE_CHAINED_DICTIONARY
signature SINGLE_CHAINED_DICTIONARY = sig include DICTIONARY val create : unit -> (''k,'v) dictionary end
structure TypeHolder
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
structure SingleChainHasEntries
structure SingleChainHasEntries = 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 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