Difference between revisions of "Chained Dictionary Assignment"
(→shell) |
|||
(77 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
=Motivation= | =Motivation= | ||
− | In this and the follow up [[Sorted_Dictionary_Assignment|Sorted Dictionary]] studio, you will build three implementations of a dictionary. Each will be | + | In this and the follow up [[Sorted_Dictionary_Assignment|Sorted Dictionary]] studio, you will build three implementations of a dictionary. Each will be an immutable data structure. |
− | |||
− | |||
− | |||
− | |||
− | + | =Reference= | |
− | + | ==SML structure [https://smlfamily.github.io/Basis/option.html Option]== | |
− | + | datatype 'a option = NONE | SOME of 'a | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | [https://smlfamily.github.io/Basis/ | ||
− | |||
− | == | ||
− | |||
− | |||
− | |||
=Code To Investigate= | =Code To Investigate= | ||
==signature Dictionary== | ==signature Dictionary== | ||
− | + | Note the [http://www.cs.cmu.edu/~rwh/isml/book.pdf#subsection.18.1.2 include] in the DICTIONARY signature. | |
+ | |||
+ | <syntaxhighlight lang="sml"> | ||
+ | signature DICTIONARY_FUNCTOR_PARAMETER = sig | ||
type (''k,'v) dictionary | 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 get : ((''k,'v) dictionary *''k) -> 'v option | ||
− | val put : ((''k,'v) dictionary *''k *'v) -> 'v option | + | val put : ((''k,'v) dictionary *''k *'v) -> (''k,'v) dictionary * 'v option |
− | val remove : ((''k,'v) dictionary *''k) -> 'v option | + | val remove : ((''k,'v) dictionary *''k) -> (''k,'v) dictionary * 'v option |
val entries : (''k,'v) dictionary -> (''k*'v) list | val entries : (''k,'v) dictionary -> (''k*'v) list | ||
+ | end | ||
+ | |||
+ | signature DICTIONARY = sig include DICTIONARY_FUNCTOR_PARAMETER | ||
val keys : (''k,'v) dictionary -> ''k list | val keys : (''k,'v) dictionary -> ''k list | ||
val values : (''k,'v) dictionary -> 'v list | val values : (''k,'v) dictionary -> 'v list | ||
− | end</ | + | end |
+ | </syntaxhighlight> | ||
+ | |||
+ | ===create=== | ||
+ | Specific to each structure. Creates an empty immutable Dictionary. | ||
===get=== | ===get=== | ||
Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#get-java.lang.Object- java.util.Map<K,V>'s get(key) method] except instead of returning null or the associated value, it returns an option. | Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#get-java.lang.Object- java.util.Map<K,V>'s get(key) method] except instead of returning null or the associated value, it returns an option. | ||
===put=== | ===put=== | ||
− | Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#put-K-V- java.util.Map<K,V>'s put(key,value) method] except instead of returning null or the previously associated value, it returns an option. | + | Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#put-K-V- 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 previously associated value (along with the updated dictionary in a 2-tuple). | ||
+ | |||
===remove=== | ===remove=== | ||
Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#remove-java.lang.Object- java.util.Map<K,V>'s remove(key) method] except instead of returning null or the previously associated value, it returns an option. | Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#remove-java.lang.Object- 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 previously associated value (along with the updated dictionary in a 2-tuple). | ||
+ | |||
===entries=== | ===entries=== | ||
Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#entrySet-- java.util.Map<K,V>'s entrySet() method]. | Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#entrySet-- java.util.Map<K,V>'s entrySet() method]. | ||
Line 60: | Line 49: | ||
===values=== | ===values=== | ||
Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#values-- java.util.Map<K,V>'s values() method]. | Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#values-- java.util.Map<K,V>'s values() method]. | ||
− | |||
=Code To Implement= | =Code To Implement= | ||
− | ==functor | + | ==functor DictionaryFn== |
− | Each implementation of dictionary can reuse the same functions which given a list of entries produce the keys and values. | + | Each implementation of dictionary can reuse the same functions which given a list of entries produce the keys and values. <code>functor DictionaryFn</code> accepts a signature parameter which defines all of the necessary functions besides <code>keys</code> and <code>values</code>. Critically, this includes the <code>entries</code> function which can be employed to support the <code>keys</code> and <code>values</code> functions. |
− | |||
− | < | ||
− | functor | ||
− | |||
− | |||
− | |||
===keys=== | ===keys=== | ||
− | One of [https://smlfamily.github.io/Basis/list.html List's | + | One of [https://smlfamily.github.io/Basis/list.html List]'s higher order functions can be useful here. Which one is it? |
− | + | <syntaxhighlight lang="sml"> | |
fun keys(dict : (''k,'v) dictionary) : ''k list = | fun keys(dict : (''k,'v) dictionary) : ''k list = | ||
− | raise Fail "NotYetImplemented"</ | + | raise Fail "NotYetImplemented" |
+ | </syntaxhighlight> | ||
===values=== | ===values=== | ||
− | One of [https://smlfamily.github.io/Basis/list.html List's | + | One of [https://smlfamily.github.io/Basis/list.html List]'s higher-order functions can be useful here. Which one is it? |
− | + | <syntaxhighlight lang="sml"> | |
fun values(dict : (''k,'v) dictionary) : 'v list = | fun values(dict : (''k,'v) dictionary) : 'v list = | ||
− | raise Fail "NotYetImplemented"</ | + | raise Fail "NotYetImplemented" |
+ | </syntaxhighlight> | ||
+ | |||
+ | ==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 ''SingleChained''Dictionary. 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. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
+ | <syntaxhighlight lang="sml"> | ||
+ | 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 | ||
+ | </syntaxhighlight> | ||
===get=== | ===get=== | ||
− | + | <syntaxhighlight lang="sml"> | |
+ | fun get(chain : (''k*'v) list, key:''k) : 'v option = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | </syntaxhighlight> | ||
===put=== | ===put=== | ||
+ | <syntaxhighlight lang="sml"> | ||
+ | fun put(chain : (''k*'v) list, key:''k, value:'v) : (''k*'v) list * 'v option = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | </syntaxhighlight> | ||
===remove=== | ===remove=== | ||
+ | <syntaxhighlight lang="sml"> | ||
+ | fun remove(chain : (''k*'v) list, key : ''k) : (''k*'v) list * 'v option = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | ==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 wants to use a mutable key which would create an invalid HashedDictionary. Whatever the reason, it seems like a reasonable and straightforward implementation of Dictionary to provide. | ||
+ | |||
+ | <syntaxhighlight lang="sml"> | ||
+ | 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) | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | [[File:Single_chained_dictionary.svg|400px]] | ||
+ | |||
+ | ===type dictionary=== | ||
+ | Change the definition of <nowiki>type (''k,'v) dictionary</nowiki> to support SingleChainedDictionary. | ||
+ | |||
+ | <syntaxhighlight lang="sml"> | ||
+ | (* TODO: replace unit with the type you decide upon *) | ||
+ | type (''k,'v) dictionary = unit | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | ===type create_parameter_type=== | ||
+ | Leave create_parameter_type unchanged. SingleChainedDictionary's create method accepts no parameters, so unit is the correct type. | ||
+ | |||
+ | <syntaxhighlight lang="sml"> | ||
+ | type ''k create_parameter_type = unit | ||
+ | </syntaxhighlight> | ||
+ | === create function === | ||
+ | <syntaxhighlight lang="sml"> | ||
+ | fun create() : (''k,'v) dictionary = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | === get === | ||
+ | <syntaxhighlight lang="sml"> | ||
+ | fun get(dict : (''k,'v) dictionary, key : ''k) : 'v option = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | remember to use the Chain structure. | ||
+ | |||
+ | === put === | ||
+ | <syntaxhighlight lang="sml"> | ||
+ | fun put(dict : (''k,'v) dictionary, key : ''k , value : 'v) : (''k,'v) dictionary * 'v option = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | remember to use the Chain structure. | ||
+ | |||
+ | === remove === | ||
+ | <syntaxhighlight lang="sml"> | ||
+ | fun remove(dict : (''k,'v) dictionary, key : ''k) : (''k,'v) dictionary * 'v option = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | </syntaxhighlight> | ||
− | + | remember to use the Chain structure. | |
− | |||
− | |||
− | |||
− | + | === 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 DictionaryFn</code>. | ||
− | = | + | <syntaxhighlight lang="sml"> |
+ | fun entries(dict : (''k,'v) dictionary) : (''k*'v) list = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | ==structure HashedDictionary== | ||
+ | ===Reference=== | ||
+ | ====Abstract Data Type==== | ||
+ | [https://en.wikipedia.org/wiki/Hash_table HashTable on Wikipedia] | ||
+ | |||
+ | <youtube>shs0KM3wKv8</youtube> | ||
[https://en.wikipedia.org/wiki/Hash_table Hash table] | [https://en.wikipedia.org/wiki/Hash_table Hash table] | ||
+ | |||
+ | ====SML structure [https://smlfamily.github.io/Basis/vector.html Vector]==== | ||
+ | # [https://smlfamily.github.io/Basis/vector.html#SIG:VECTOR.tabulate:VAL tabulate] <code>: int * (int -> 'a) -> 'a vector</code> | ||
+ | # [https://smlfamily.github.io/Basis/vector.html#SIG:VECTOR.length:VAL length] <code>: 'a vector -> int</code> | ||
+ | # [https://smlfamily.github.io/Basis/vector.html#SIG:VECTOR.sub:VAL sub] <code>: a vector * int -> 'a</code> | ||
+ | # [https://smlfamily.github.io/Basis/vector.html#SIG:VECTOR.update:VAL update] <code>: 'a vector * int * 'a -> 'a vector</code> | ||
+ | # [https://smlfamily.github.io/Basis/vector.html#SIG:VECTOR.foldl:VAL foldl] <code>: ('a * 'b -> 'b) -> 'b -> 'a vector -> 'b</code> | ||
+ | |||
+ | === shell === | ||
+ | <syntaxhighlight lang="sml"> | ||
+ | structure HashedDictionary = DictionaryFn(struct | ||
+ | type ''k hash_function = ''k -> int | ||
+ | |||
+ | (* TODO: replace unit with the type you decide upon *) | ||
+ | type (''k,'v) dictionary = unit | ||
+ | |||
+ | type ''k create_parameter_type = (int * (''k hash_function)) | ||
+ | |||
+ | fun create(bucket_count_request : int, hash : ''k hash_function) : (''k,'v) dictionary = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | |||
+ | 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 getChainForKey(dict : (''k,'v) dictionary, key : ''k) : (''k*'v) list = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | |||
+ | fun updateChainForKey(dict : (''k,'v) dictionary, key : ''k, updater_function) : (''k,'v) dictionary * 'v option = | ||
+ | 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) | ||
+ | </syntaxhighlight> | ||
[[File:Hash table 5 0 1 1 1 1 1 LL.svg]] | [[File:Hash table 5 0 1 1 1 1 1 LL.svg]] | ||
− | + | ===type dictionary=== | |
+ | Change the definition of <nowiki>type (''k,'v) dictionary</nowiki> to support HashedDictionary. | ||
− | < | + | <syntaxhighlight lang="sml"> |
− | + | (* TODO: replace unit with the type you decide upon *) | |
− | + | type (''k,'v) dictionary = unit | |
− | + | </syntaxhighlight> | |
+ | |||
+ | ===type create_parameter_type=== | ||
+ | Leave create_parameter_type unchanged. HashedDictionary's create method accepts two parameters: an int for the requested bucket count and a hash_function. | ||
+ | |||
+ | <syntaxhighlight lang="sml"> | ||
+ | type ''k create_parameter_type = (int * (''k hash_function)) | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | === create === | ||
+ | <syntaxhighlight lang="sml"> | ||
+ | fun create() : (''k,'v) dictionary = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | === positive_remainder === | ||
+ | Hash codes can be negative. Vector indices cannot. Use this function to ensure a valid index. | ||
+ | |||
+ | <syntaxhighlight lang="sml"> | ||
+ | fun positive_remainder(v : int, n : int) : int = | ||
+ | let | ||
+ | val result = v mod n | ||
+ | in | ||
+ | if result >= 0 then result else result+n | ||
+ | end | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | === get === | ||
+ | <syntaxhighlight lang="sml"> | ||
+ | fun get(dict : (''k,'v) dictionary, key : ''k) : 'v option = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | remember to use the Chain structure. | ||
+ | |||
+ | === put === | ||
+ | <syntaxhighlight lang="sml"> | ||
+ | fun put(dict : (''k,'v) dictionary, key : ''k , value : 'v) : (''k,'v) dictionary * 'v option = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | remember to use the Chain structure. | ||
+ | |||
+ | === remove === | ||
+ | <syntaxhighlight lang="sml"> | ||
+ | fun remove(dict : (''k,'v) dictionary, key : ''k) : (''k,'v) dictionary * 'v option = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | remember to use the Chain structure. | ||
+ | |||
+ | === 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 DictionaryFn</code>. | ||
+ | |||
+ | <syntaxhighlight lang="sml"> | ||
+ | fun entries(dict : (''k,'v) dictionary) : (''k*'v) list = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | </syntaxhighlight> | ||
=Testing= | =Testing= | ||
− | + | {{SMLUnitTesting|run_chained_testing|dictionary/chained}} | |
− | |||
− | |||
− | |||
=Pledge, Acknowledgments, Citations= | =Pledge, Acknowledgments, Citations= | ||
− | {{Pledge| | + | {{Pledge|exercise-chained-dictionary}} |
Latest revision as of 19:35, 14 July 2023
Contents
Motivation
In this and the follow up Sorted Dictionary studio, you will build three implementations of a dictionary. Each will be an immutable data structure.
Reference
SML structure Option
datatype 'a option = NONE | SOME of 'a
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 previously associated 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 previously associated 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 wants to use a mutable key which would create an invalid HashedDictionary. Whatever the reason, it seems like a reasonable and straightforward implementation of Dictionary to provide.
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 dictionary
Change the definition of type (''k,'v) dictionary to support SingleChainedDictionary.
(* TODO: replace unit with the type you decide upon *)
type (''k,'v) dictionary = unit
type create_parameter_type
Leave create_parameter_type unchanged. SingleChainedDictionary's create method accepts no parameters, so unit is the correct type.
type ''k create_parameter_type = unit
create function
fun create() : (''k,'v) dictionary =
raise Fail "NotYetImplemented"
get
fun get(dict : (''k,'v) dictionary, key : ''k) : 'v option =
raise Fail "NotYetImplemented"
remember to use the Chain structure.
put
fun put(dict : (''k,'v) dictionary, key : ''k , value : 'v) : (''k,'v) dictionary * 'v option =
raise Fail "NotYetImplemented"
remember to use the Chain structure.
remove
fun remove(dict : (''k,'v) dictionary, key : ''k) : (''k,'v) dictionary * 'v option =
raise Fail "NotYetImplemented"
remember to use the Chain structure.
entries
Define the entries method so we can take advantage of the keys
and values
functions you implemented on functor DictionaryFn
.
fun entries(dict : (''k,'v) dictionary) : (''k*'v) list =
raise Fail "NotYetImplemented"
structure HashedDictionary
Reference
Abstract Data Type
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
shell
structure HashedDictionary = DictionaryFn(struct
type ''k hash_function = ''k -> int
(* TODO: replace unit with the type you decide upon *)
type (''k,'v) dictionary = unit
type ''k create_parameter_type = (int * (''k hash_function))
fun create(bucket_count_request : int, hash : ''k hash_function) : (''k,'v) dictionary =
raise Fail "NotYetImplemented"
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 getChainForKey(dict : (''k,'v) dictionary, key : ''k) : (''k*'v) list =
raise Fail "NotYetImplemented"
fun updateChainForKey(dict : (''k,'v) dictionary, key : ''k, updater_function) : (''k,'v) dictionary * 'v option =
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 dictionary
Change the definition of type (''k,'v) dictionary to support HashedDictionary.
(* TODO: replace unit with the type you decide upon *)
type (''k,'v) dictionary = unit
type create_parameter_type
Leave create_parameter_type unchanged. HashedDictionary's create method accepts two parameters: an int for the requested bucket count and a hash_function.
type ''k create_parameter_type = (int * (''k hash_function))
create
fun create() : (''k,'v) dictionary =
raise Fail "NotYetImplemented"
positive_remainder
Hash codes can be negative. Vector indices cannot. Use this function to ensure a valid index.
fun positive_remainder(v : int, n : int) : int =
let
val result = v mod n
in
if result >= 0 then result else result+n
end
get
fun get(dict : (''k,'v) dictionary, key : ''k) : 'v option =
raise Fail "NotYetImplemented"
remember to use the Chain structure.
put
fun put(dict : (''k,'v) dictionary, key : ''k , value : 'v) : (''k,'v) dictionary * 'v option =
raise Fail "NotYetImplemented"
remember to use the Chain structure.
remove
fun remove(dict : (''k,'v) dictionary, key : ''k) : (''k,'v) dictionary * 'v option =
raise Fail "NotYetImplemented"
remember to use the Chain structure.
entries
Define the entries method so we can take advantage of the keys
and values
functions you implemented on functor DictionaryFn
.
fun entries(dict : (''k,'v) dictionary) : (''k*'v) list =
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