Difference between revisions of "Chained Dictionary Assignment"
(→values) |
|||
Line 42: | Line 42: | ||
Each implementation of dictionary can reuse the same functions which given a list of entries produce the keys and values. <code>functor HasEntriesFn</code> accepts a signature parameter which defines an entries function to support <code>keys</code> and <code>values</code> functions. | Each implementation of dictionary can reuse the same functions which given a list of entries produce the keys and values. <code>functor HasEntriesFn</code> accepts a signature parameter which defines an entries function to support <code>keys</code> and <code>values</code> functions. | ||
− | <nowiki> | + | <nowiki>functor HasEntriesFn (HasEntriesParameter : sig |
− | functor HasEntriesFn (HasEntriesParameter : sig | ||
type (''k,'v) dictionary | type (''k,'v) dictionary | ||
val entries : (''k,'v) dictionary -> (''k*'v) list | val entries : (''k,'v) dictionary -> (''k*'v) list | ||
Line 49: | Line 48: | ||
===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? |
− | <nowiki> | + | <nowiki>fun keys(dict : (''k,'v) dictionary) : ''k list = |
− | fun keys(dict : (''k,'v) dictionary) : ''k list = | ||
raise Fail "NotYetImplemented"</nowiki> | raise Fail "NotYetImplemented"</nowiki> | ||
Line 58: | Line 56: | ||
One of [https://smlfamily.github.io/Basis/list.html List]'s higher-order functions can be useful here. Which one is it? | One of [https://smlfamily.github.io/Basis/list.html List]'s higher-order functions can be useful here. Which one is it? | ||
− | <nowiki> | + | <nowiki>fun values(dict : (''k,'v) dictionary) : 'v list = |
− | fun values(dict : (''k,'v) dictionary) : 'v list = | ||
raise Fail "NotYetImplemented"</nowiki> | raise Fail "NotYetImplemented"</nowiki> | ||
Revision as of 14:21, 2 March 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
ref
fun get_value_at_reference(reference : 'a ref) : 'a = !reference fun set_value_at_reference(reference : 'a ref, next_value : 'a) : 'a = let val previous_value = !reference val _ = reference := next_value in previous_value end (* alternate version fun set_value_at_reference(reference : 'a ref, next_value : 'a) : 'a = let val previous_value = !reference in ( reference := next_value ; previous_value ) end *)
Mutable Array
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
File:Hash table 5 0 1 1 1 1 1 LL.svg
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