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

Refs and Arrays

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

HasEntriesFn

functor HasEntriesFn (HasEntriesParameter : sig
	type (''k,'v) dictionary
	val entries : (''k,'v) dictionary -> (''k*'v) list
end) : HAS_ENTRIES = struct
	open HasEntriesParameter

    fun keys(dict : (''k,'v) dictionary) : ''k list = 
        (* <SOLUTION> *)
        if true
        then
	        List.map (fn(key,_)=>key) (entries(dict))
        else (* </SOLUTION> *)raise Fail "NotYetImplemented"

    fun values(dict : (''k,'v) dictionary) : 'v list = 
        (* <SOLUTION> *)
        if true
        then
	        List.map (fn(_,value)=>value) (entries(dict))
        else (* </SOLUTION> *)raise Fail "NotYetImplemented"
end

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

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