Chained Dictionary Assignment
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
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 *)
Dictionary
Signature
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
Spec
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.
DictionaryUtils
All three implementations of dictionary can reuse the same functions which given a list of entries produce the keys and values.
One of List's higher order functions can be useful here. Which one is it?
fun entries_to_keys(entries : (''k*'v) list) : ''k list = raise NotYetImplemented fun entries_to_values(entries : (''k*'v) list) : 'v list = raise NotYetImplemented
ListOfEntries (Optional But Encouraged)
While it is not required, both the SingleList and Hashtable implementations will have a lot of overlap. Building the common functionality will allow you to reuse this code. Further, some students have reported the separation helping with wrangling the references in the dictionaries.
fun list_get(entries : (''k*'v) list, key : ''k) : 'v option = raise NotYetImplemented fun list_put(entries : (''k*'v) list, key : ''k, value : 'v) : 'v option * (''k * 'v) list= raise NotYetImplemented fun list_remove(entries : (''k*'v) list, key : ''k) : 'v option * (''k * 'v) list = raise NotYetImplemented
NOTE: You may change this file. For example, if you decide to go with a mutable key-value pair for your single-list and hash dictionaries, feel free to change this module to match what you need.
SingleList Implementation
signature SINGLE_LIST_DICTIONARY = sig include DICTIONARY val create : unit -> (''k,'v) dictionary end
Hashtable Implementation
signature HASHED_DICTIONARY = sig include DICTIONARY type ''k hash_function = ''k -> int val create_hashed : (int * ''k hash_function) -> (''k,'v) dictionary end
Testing
file: sml renovated_unit_test_single_list_and_hashed.sml
in folder: src/test/sml/dictionary/single_list_and_hashed
Pledge, Acknowledgments, Citations
file: | studio-dictionary-pledge-acknowledgments-citations.txt |
More info about the Honor Pledge