Difference between revisions of "Chained Dictionary Assignment"

From CSE425S Wiki
Jump to navigation Jump to search
Line 2: Line 2:
 
In this and the follow up [[Sorted_Dictionary_Assignment|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 [http://sml-family.org/Basis/general.html#SIG:GENERAL.!:VAL ref] feature of SML, either directly or via the mutable [http://sml-family.org/Basis/array.html Array structure].
 
In this and the follow up [[Sorted_Dictionary_Assignment|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 [http://sml-family.org/Basis/general.html#SIG:GENERAL.!:VAL ref] feature of SML, either directly or via the mutable [http://sml-family.org/Basis/array.html Array structure].
  
 +
 +
=Background=
 +
[https://www.cs.cornell.edu/courses/cs312/2008sp/recitations/rec15.html Refs and Arrays]
 +
 +
=Permission=
 +
You may invoke remove from put and get from remove if it will make your implementation cleaner.
 +
 +
=Dictionary=
 +
==Signature==
 
  <nowiki>signature DICTIONARY = sig
 
  <nowiki>signature DICTIONARY = sig
 
     type (''k,'v) dictionary
 
     type (''k,'v) dictionary
Line 11: Line 20:
 
     val values : (''k,'v) dictionary -> 'v list
 
     val values : (''k,'v) dictionary -> 'v list
 
end</nowiki>
 
end</nowiki>
 
+
==Spec==
=Background=
+
===get===
[https://www.cs.cornell.edu/courses/cs312/2008sp/recitations/rec15.html Refs and Arrays]
 
 
 
=Permission=
 
You may invoke remove from put and get from remove if it will make your implementation cleaner.
 
 
 
=Spec=
 
==get==
 
 
Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#get-java.lang.Object- java.util.Map<K,V>'s get(key) method] except instead of returning null or the associated value, it returns an option.
 
Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#get-java.lang.Object- java.util.Map<K,V>'s get(key) method] except instead of returning null or the associated value, it returns an option.
==put==
+
===put===
 
Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#put-K-V- java.util.Map<K,V>'s put(key,value) method] except instead of returning null or the previously associated value, it returns an option.
 
Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#put-K-V- 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==
+
===remove===
 
Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#remove-java.lang.Object- java.util.Map<K,V>'s remove(key) method] except instead of returning null or the previously associated value, it returns an option.
 
Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#remove-java.lang.Object- java.util.Map<K,V>'s remove(key) method] except instead of returning null or the previously associated value, it returns an option.
==entries==
+
===entries===
 
Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#entrySet-- java.util.Map<K,V>'s entrySet() method].
 
Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#entrySet-- java.util.Map<K,V>'s entrySet() method].
==keys==
+
===keys===
 
Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#keySet-- java.util.Map<K,V>'s keySet() method].
 
Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#keySet-- java.util.Map<K,V>'s keySet() method].
==values==
+
===values===
 
Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#values-- java.util.Map<K,V>'s values() method].
 
Behaves much like [https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#values-- java.util.Map<K,V>'s values() method].
  

Revision as of 19:47, 2 March 2020

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

Permission

You may invoke remove from put and get from remove if it will make your implementation cleaner.

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

ListOfEntries (Optional But Encouraged)

While it is not required, both the SingleList and Hashtable implementations will have a lot of overlap. Building the common functionality will allow you to reuse this code. Further, some students have reported the separation helping with wrangling the references in the dictionaries.

    exception KeyNotFound
    fun internal_remove(entries : (''k*'v) list, key : ''k) : 'v option * (''k * 'v) list =
        raise NotYetImplemented

    fun list_get(entries : (''k*'v) list, key : ''k) : 'v option = 
        raise NotYetImplemented

    fun list_put(entries : (''k*'v) list, key : ''k, value : 'v) : 'v option * (''k * 'v) list=
        raise NotYetImplemented

    fun list_remove(entries : (''k*'v) list, key : ''k) : 'v option * (''k * 'v) list =
        raise NotYetImplemented

SingleList Implementation

signature SINGLE_LIST_DICTIONARY = sig include DICTIONARY
    val create_simple : 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