Difference between revisions of "Chained Dictionary Assignment"

From CSE425S Wiki
Jump to navigation Jump to search
 
(45 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 a persistent, mutable data structure, so you can expect to use the [https://smlfamily.github.io/Basis/general.html#SIG:GENERAL.!:VAL ref] feature of SML, either directly or via the mutable [https://smlfamily.github.io/Basis/array.html Array structure].
+
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.
=Background=
 
==SML==
 
===Vector===
 
[https://smlfamily.github.io/Basis/vector.html SML Vector structure]
 
  
==HashTable==
+
=Reference=
[https://en.wikipedia.org/wiki/Hash_table HashTable on Wikipedia]
+
==SML structure [https://smlfamily.github.io/Basis/option.html Option]==
 
+
datatype 'a option = NONE | SOME of 'a
<youtube>shs0KM3wKv8</youtube>
 
  
 
=Code To Investigate=
 
=Code To Investigate=
 
==signature Dictionary==
 
==signature Dictionary==
<nowiki>signature DICTIONARY = sig
+
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</nowiki>
+
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 36: Line 51:
  
 
=Code To Implement=
 
=Code To Implement=
==functor HasEntriesFn==
+
==functor DictionaryFn==
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 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.
 
 
  <nowiki>functor HasEntriesFn (HasEntriesParameter : sig
 
type (''k,'v) dictionary
 
val entries : (''k,'v) dictionary -> (''k*'v) list
 
end) : HAS_ENTRIES = struct</nowiki>
 
  
 
===keys===
 
===keys===
 
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>fun keys(dict : (''k,'v) dictionary) : ''k list =  
+
<syntaxhighlight lang="sml">
raise Fail "NotYetImplemented"</nowiki>
+
fun keys(dict : (''k,'v) dictionary) : ''k list =  
 +
raise Fail "NotYetImplemented"
 +
</syntaxhighlight>
  
 
===values===
 
===values===
 
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>fun values(dict : (''k,'v) dictionary) : 'v list =  
+
<syntaxhighlight lang="sml">
raise Fail "NotYetImplemented"</nowiki>
+
fun values(dict : (''k,'v) dictionary) : 'v list =  
 +
raise Fail "NotYetImplemented"
 +
</syntaxhighlight>
  
==functor HasChainingFn==
+
==structure Chain==
One can anticipate that separate structures for <code>SingleChainedDictionary</code> and <code>HashedDictionary</code> have potential for code resuseBy parameterizing <code>functor HasChainingFn</code> with <code>getChainOfEntriesForKey</code> and <code>setChainOfEntriesForKey</code> we can implement <code>get</code>, <code>put</code>, and <code>remove</code>.
+
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.
  
<nowiki>functor HasChainingFn (HasChainingParameter : sig
+
We implement structure Chain so we can use the code in both SingleChainedDictionary and HashedDictionary.
type (''k,'v) dictionary
+
 
val getChainOfEntriesForKey : ((''k,'v) dictionary * ''k) -> (''k*'v) list
+
<syntaxhighlight lang="sml">
val setChainOfEntriesForKey : ((''k,'v) dictionary * ''k * (''k*'v) list) -> unit
+
signature CHAIN = sig
end) : HAS_CHAINING = struct</nowiki>
+
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==
 
==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.
+
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.
  
=== signature SINGLE_CHAINED_DICTIONARY ===
+
<syntaxhighlight lang="sml">
We can see that <code>signature SINGLE_CHAINED_DICTIONARY</code> includes <code>DICTIONARY</code> and adds a <code>create</code> function.
+
structure SingleChainedDictionary = DictionaryFn(struct
 +
   
 +
    (* TODO: replace unit with the type you decide upon *)
 +
    type (''k,'v) dictionary = unit
  
<nowiki>structure SingleChainedDictionary :> SINGLE_CHAINED_DICTIONARY</nowiki>
+
    type ''k create_parameter_type = unit
 +
   
 +
    fun create() : (''k,'v) dictionary =
 +
        raise Fail "NotYetImplemented"
  
<nowiki>signature SINGLE_CHAINED_DICTIONARY = sig include DICTIONARY
+
     fun get(dict : (''k,'v) dictionary, key : ''k) : 'v option =
     val create : unit -> (''k,'v) dictionary
+
        raise Fail "NotYetImplemented"
end</nowiki>
 
  
=== structure TypeHolder ===
+
    fun put(dict : (''k,'v) dictionary, key : ''k , value : 'v) : (''k,'v) dictionary * 'v option =
Change the definition of <code>type (''k,'v) dictionary</code> to support SingleChainedDictionary.
+
        raise Fail "NotYetImplemented"
 +
 +
    fun remove(dict : (''k,'v) dictionary, key : ''k) : (''k,'v) dictionary * 'v option =
 +
        raise Fail "NotYetImplemented"
  
<nowiki>structure TypeHolder = struct
+
    fun entries(dict : (''k,'v) dictionary) : (''k*'v) list =
(* TODO: replace unit with the type you decide upon *)
+
        raise Fail "NotYetImplemented"
type (''k,'v) dictionary = unit
+
 
end</nowiki>
+
end)
 +
</syntaxhighlight>
  
 
[[File:Single_chained_dictionary.svg|400px]]
 
[[File:Single_chained_dictionary.svg|400px]]
  
=== structure SingleChainHasEntries ===
+
===type dictionary===
<nowiki>structure SingleChainHasEntries = HasEntriesFn (struct
+
Change the definition of <nowiki>type (''k,'v) dictionary</nowiki> to support SingleChainedDictionary.
type (''k,'v) dictionary = (''k,'v) TypeHolder.dictionary
+
 
fun entries(dict : (''k,'v) dictionary) : (''k*'v) list =
+
<syntaxhighlight lang="sml">
raise Fail "NotYetImplemented"
+
(* TODO: replace unit with the type you decide upon *)
end)</nowiki>
+
type (''k,'v) dictionary = unit
====entries====
+
</syntaxhighlight>
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>.
+
 
 +
===type create_parameter_type===
 +
Leave create_parameter_type unchanged.  SingleChainedDictionary's create method accepts no parameters, so unit is the correct type.
  
=== structure SingleChainHasChaining ===
+
<syntaxhighlight lang="sml">
 +
type ''k create_parameter_type = unit
 +
</syntaxhighlight>
 +
=== create function ===
 +
<syntaxhighlight lang="sml">
 +
fun create() : (''k,'v) dictionary =
 +
raise Fail "NotYetImplemented"
 +
</syntaxhighlight>
  
The two functions <code>getChainOfEntriesForKey(dict, key)</code> and <code>setChainOfEntriesForKey(dict, key, nextEntries)</code> used to parameterize <code>functor>HasChainingFn</code> 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).
+
=== get ===
 +
<syntaxhighlight lang="sml">
 +
fun get(dict : (''k,'v) dictionary, key : ''k) : 'v option =
 +
raise Fail "NotYetImplemented"
 +
</syntaxhighlight>
  
<nowiki>structure SingleChainHasChaining = HasChainingFn (struct
+
remember to use the Chain structure.
type (''k,'v) dictionary = (''k,'v) TypeHolder.dictionary
 
  
fun getChainOfAllEntries(dict : (''k,'v) dictionary) : (''k*'v) list =
+
=== put ===
raise Fail "NotYetImplemented"
+
<syntaxhighlight lang="sml">
 +
fun put(dict : (''k,'v) dictionary, key : ''k , value : 'v) : (''k,'v) dictionary * 'v option =
 +
raise Fail "NotYetImplemented"
 +
</syntaxhighlight>
  
fun setChainOfAllEntries(dict : (''k,'v) dictionary, nextEntries : (''k*'v) list) : unit =
+
remember to use the Chain structure.
raise Fail "NotYetImplemented"
 
  
fun getChainOfEntriesForKey(dict : (''k,'v) dictionary, key : ''k) : (''k*'v) list =
+
=== remove ===
getChainOfAllEntries(dict)
+
<syntaxhighlight lang="sml">
 +
fun remove(dict : (''k,'v) dictionary, key : ''k) : (''k,'v) dictionary * 'v option =
 +
raise Fail "NotYetImplemented"
 +
</syntaxhighlight>
  
fun setChainOfEntriesForKey(dict : (''k,'v) dictionary, key : ''k, nextEntries : (''k*'v) list) : unit =
+
remember to use the Chain structure.
setChainOfAllEntries(dict, nextEntries)
 
end)</nowiki>
 
  
====getChainOfAllEntries====
+
=== entries ===
Note: this function is called from getChainOfEntriesForKey, dropping the unnecessary key paremeter. 
+
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>.
====setChainOfAllEntries====
 
Note: this function is called from setChainOfEntriesForKey, dropping the unnecessary key paremeter.
 
  
=== create function ===
+
<syntaxhighlight lang="sml">
<nowiki>fun create() : (''k,'v) dictionary =  
+
fun entries(dict : (''k,'v) dictionary) : (''k*'v) list =
raise Fail "NotYetImplemented"</nowiki>
+
raise Fail "NotYetImplemented"
 +
</syntaxhighlight>
  
 
==structure HashedDictionary==
 
==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]
  
=== signature HASHED_DICTIONARY ===
+
====SML structure [https://smlfamily.github.io/Basis/vector.html Vector]====
We can see that <code>signature HASHED_DICTIONARY</code> includes <code>DICTIONARY</code> and adds a <code>create</code> function which accepts the number of buckets to create along with a hash function.
+
# [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))
  
<nowiki>structure HashedDictionary :> HASHED_DICTIONARY</nowiki>
+
    fun create(bucket_count_request : int, hash : ''k hash_function) : (''k,'v) dictionary =
 +
        raise Fail "NotYetImplemented"
  
<nowiki>signature HASHED_DICTIONARY = sig include DICTIONARY
+
    fun positive_remainder(v : int, n : int) : int =
     type ''k hash_function = ''k -> int
+
        let
     val create : (int * ''k hash_function) -> (''k,'v) dictionary
+
            val result = v mod n
end</nowiki>
+
        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>
  
=== structure TypeHolder ===
 
 
[[File:Hash table 5 0 1 1 1 1 1 LL.svg]]
 
[[File:Hash table 5 0 1 1 1 1 1 LL.svg]]
  
[https://smlfamily.github.io/Basis/array.html SML Array Structure]
+
===type dictionary===
 +
Change the definition of <nowiki>type (''k,'v) dictionary</nowiki> to support HashedDictionary.
  
Change the definition of <code>type (''k,'v) dictionary</code> to support HashedDictionary.
+
<syntaxhighlight lang="sml">
 +
(* TODO: replace unit with the type you decide upon *)
 +
type (''k,'v) dictionary = unit
 +
</syntaxhighlight>
  
<nowiki>structure TypeHolder = struct
+
===type create_parameter_type===
(* TODO: replace unit with the type you decide upon *)
+
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,'v) dictionary = unit
 
end</nowiki>
 
  
[[File:Single_chained_dictionary.svg|400px]]
+
<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>
  
=== structure HashedHasEntries ===
+
=== get ===
<nowiki>structure HashedHasEntries = HasEntriesFn (struct
+
<syntaxhighlight lang="sml">
type (''k,'v) dictionary = (''k,'v) TypeHolder.dictionary
+
fun get(dict : (''k,'v) dictionary, key : ''k) : 'v option =  
fun entries(dict : (''k,'v) dictionary) : (''k*'v) list =
+
raise Fail "NotYetImplemented"
raise Fail "NotYetImplemented"
+
</syntaxhighlight>
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>.
 
  
=== structure HashedHasChaining ===
+
remember to use the Chain structure.
  
<nowiki>structure HashedHasChaining = HasChainingFn (struct
+
=== put ===
type (''k,'v) dictionary = (''k,'v) TypeHolder.dictionary
+
<syntaxhighlight lang="sml">
 +
fun put(dict : (''k,'v) dictionary, key : ''k , value : 'v) : (''k,'v) dictionary * 'v option =
 +
raise Fail "NotYetImplemented"
 +
</syntaxhighlight>
  
fun positive_remainder(v : int, n : int) : int =
+
remember to use the Chain structure.
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 =
+
=== remove ===
raise Fail "NotYetImplemented"
+
<syntaxhighlight lang="sml">
 +
fun remove(dict : (''k,'v) dictionary, key : ''k) : (''k,'v) dictionary * 'v option =
 +
raise Fail "NotYetImplemented"
 +
</syntaxhighlight>
  
fun setChainOfEntriesForKey(dict : (''k,'v) dictionary, key : ''k, nextEntries : (''k*'v) list) : unit =
+
remember to use the Chain structure.
raise Fail "NotYetImplemented"
 
end)</nowiki>
 
  
====getChainOfEntriesForKey====
+
=== entries ===
====setChainOfEntriesForKey====
+
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>.
  
=== create function ===
+
<syntaxhighlight lang="sml">
<nowiki>fun create(bucket_count_request : int, hash : ''k hash_function) : (''k,'v) dictionary =  
+
fun entries(dict : (''k,'v) dictionary) : (''k*'v) list =
raise Fail "NotYetImplemented"</nowiki>
+
raise Fail "NotYetImplemented"
 +
</syntaxhighlight>
  
 
=Testing=
 
=Testing=

Latest revision as of 19:35, 14 July 2023

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

  1. instead of mutating the provided dictionary, it returns an immutable updated dictionary.
  2. 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.

  1. instead of mutating the provided dictionary, it returns an immutable updated dictionary.
  2. 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)

Single chained dictionary.svg

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

HashTable on Wikipedia

Hash table

SML structure Vector

  1. tabulate : int * (int -> 'a) -> 'a vector
  2. length : 'a vector -> int
  3. sub : a vector * int -> 'a
  4. update : 'a vector * int * 'a -> 'a vector
  5. 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)

Hash table 5 0 1 1 1 1 1 LL.svg

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.

SML Error Messages

Pledge, Acknowledgments, Citations

file: exercise-chained-dictionary-pledge-acknowledgments-citations.txt

More info about the Honor Pledge