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

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

SingleChained Implementation

signature SINGLE_CHAINED_DICTIONARY = sig include DICTIONARY
    val create : unit -> (''k,'v) dictionary
end

Hashtable Implementation

Hash table

SML Array Structure

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 run_chained_testing.sml

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

Pledge, Acknowledgments, Citations

file:

studio-dictionary-pledge-acknowledgments-citations.txt

More info about the Honor Pledge