Difference between revisions of "Chained Dictionary Assignment"

From CSE425S Wiki
Jump to navigation Jump to search
Line 68: Line 68:
 
type (''k,'v) dictionary
 
type (''k,'v) dictionary
 
val entries : (''k,'v) dictionary -> (''k*'v) list
 
val entries : (''k,'v) dictionary -> (''k*'v) list
end) : HAS_ENTRIES = struct
+
end) : HAS_ENTRIES = struct</nowiki>
open HasEntriesParameter
 
 
 
fun keys(dict : (''k,'v) dictionary) : ''k list =
 
raise Fail "NotYetImplemented"
 
 
 
fun values(dict : (''k,'v) dictionary) : 'v list =
 
raise Fail "NotYetImplemented"
 
end</nowiki>
 
  
 
===keys===
 
===keys===

Revision as of 18:46, 28 February 2022

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

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

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

Hash table 5 0 1 1 1 1 1 LL.svg

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