Creating A Dictionary In SML

Question

I am newly Learner Of The SML Language. I Have Learned The Basics Of SML Language.But, I am having a Trouble In getting the code of creating a dictionary in SML. So, I Want To Know The code.

Answer 1

You can start by defining a signature for your dictionary:

signature DICT =
sig
  type (''k, 'v) dict

  val empty : (''k, 'v) dict
  val insert : ''k -> 'v -> (''k, 'v) dict -> (''k, 'v) dict
  val lookup : ''k -> (''k, 'v) dict -> 'v option
end

The ''k (an equality type) assumes that the only thing I need to know about the key of a key-value store is that it can be compared for equality, so that I can find the right key when looking. This allows me to build a simple list-based dictionary with O(n) insert and lookup:

structure ListDict : DICT =
struct
  type (''k, 'v) dict = (''k * 'v) list

  val empty = []

  fun insert k v [] = [(k, v)]
    | insert k v ((k2,v2) :: rest) =
      if k = k2 then (k,v) :: rest else (k2,v2) :: insert k v rest

  fun lookup k [] = NONE
    | lookup k ((k2, v) :: rest) =
      if k = k2 then SOME v else lookup k rest
end

The type-level restriction of ''k means that I can't, for example, represent my dictionary as a binary search tree, since ordering things (less than, equal to, greater than) is not a property of equality types, or represent my dictionary as a hashtable, since finding the hash of a value is also not a property of equality types.

So I might instead like that keys can be ordered or hashed. Unfortunately SML does not have a built-in class of types that are orderable or hashable like it has equality types. A way to overcome this limitation is to change the interface so that a comparison or hash function is passed to the module. Here's how that might look for comparison:

signature ORD =
sig
  type t
  val compare : t -> t -> order
end

signature DICT =
sig
  type k
  type 'v dict

  val empty : 'v dict
  val insert : k -> 'v -> 'v dict -> 'v dict
  val lookup : k -> 'v dict -> 'v option
end

This allows me, for example, to write a dictionary structure based on binary trees:

functor TreeDict (Ord : ORD) : DICT =
struct
  type k = Ord.t
  datatype 'v dict = Leaf | Node of k * 'v * 'v dict * 'v dict

  val empty = Leaf

  fun insert k v Leaf = Node (k, v, Leaf, Leaf)
    | insert k v (Node (k2, v2, left, right)) =
      case Ord.compare (k, k2) of
           EQ => Node (k, v, left, right)
         | LT => Node (k2, v2, insert k v left, right)
         | GT => Node (k2, v2, left, insert k v right)

  fun lookup k Leaf = NONE
    | lookup k (Node (k2, v, left, right)) =
      case Ord.compare (k, k2) of
           EQ => SOME v
         | GT => lookup k right
         | LT => lookup k left
end

The downside is that I have to be specific about what ORD I want.

E.g. a tree-based dictionary where the key is int may be made like this:

structure IntTreeDict = TreeDict(
  struct
    type t = int
    val compare = Int.compare
  end)