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 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

SML structure Option

datatype 'a option = NONE | SOME of 'a

HashTable

HashTable on Wikipedia

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 associate 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 associate 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 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.

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)

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.

SML Error Messages

Pledge, Acknowledgments, Citations

file:

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

More info about the Honor Pledge