用SML创建词典

Question

我是SML语言的新学习者。我已经学习了SML Language.But的基本知识，在获得在SML中创建字典的代码时遇到了困难。所以我想知道密码。

Answer 1

您可以从为字典定义签名开始：

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

''k (相等类型)假定，关于键值存储的键，我需要知道的唯一事情是可以比较它是否相等，以便在查找时能够找到正确的键。这允许我构建一个简单的基于列表的字典，其中包含O(n)插入和查找：

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

例如，''k的类型级别限制意味着我不能将字典表示为二进制搜索树，因为排序对象(小于、等于、大于)不是相等类型的属性，或者将我的字典表示为哈希表，因为查找值的散列也不是相等类型的属性。

所以我可能会希望钥匙可以被订购或者散列。不幸的是，SML没有一个内置的类型类，这些类型是可排序的或者是可接受的，就像它有相等的类型一样。克服这一限制的一种方法是更改接口，以便将比较或哈希函数传递给模块。下面是比较的方法：

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

例如，这允许我编写基于二叉树的字典结构：

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

缺点是，我必须对我想要的ORD做具体说明。

例如，键为int的基于树的字典可能如下所示：

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