Chained Dictionary Assignment

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

SML Array structure

HashTable

HashTable on Wikipedia

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

Hash table

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

SML Array Structure

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

file: sml run_chained_testing.sml

in folder: src/test/sml/dictionary/chained

Pledge, Acknowledgments, Citations

file:

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

More info about the Honor Pledge