如何在 SML/NJ 中创建和使用我自己的 structure/signature？

Question

我是函数式编程的新手，我想创建自己的 structure/signature 名为 Dictionary。到目前为止，我在名为 dictionary-en.sml:

的文件中有这个

(* The signature DICTIONARY defines a type and a programming interface for
   the dictionary data structure. The data structure allows us to store
   data in the form of (key, value) pairs and to query the data using a key. *)
signature DICTIONARY =
sig

    (* The structure has to implement a dictionary type. It defines key type,
       which has to support equality checking, and a value type for the data
       stored in the dictionary. *)
    type (''key, 'value) dict

    (* Creates an empty dictionary. *)
    val empty: (''key, 'value) dict

    (* Returns true if a key exists in the dictionary. *)
    val exists: (''key, 'value) dict -> ''key -> bool

end

我在文件中有这个 solution.sml:

structure Dictionary :> DICTIONARY =
struct
    type (''key, 'value) dict = (''key * 'value) list

    val empty = []

    fun exists dict key =
        case dict of
            [] => false
          | (k, _ )::rep => if k = key
                            then true
                            else exists rep key
end

但我不知道如何使用它。当我在 REPL 中写道：

- Dictionary.exists [(3,"c"), (5, "e"), (7, "g")] 3;

我收到这个错误：

stdIn:1.2-3.7 Error: operator and operand do not agree [tycon mismatch]
  operator domain: (''Z,'Y) Dictionary.dict
  operand:         ([int ty] * string) list
  in expression:
    Dictionary.exists ((3,"c") :: (5,"e") :: (<exp>,<exp>) :: nil)

有人可以帮助我吗？我不知道我做错了什么。

Answer 1

您无法访问内部表示；整个接口由签名给出。
您需要在签名中添加某种方式来创建字典，而不依赖于特定结构中使用的表示形式。

例如，

val insert : (''key * 'value) -> (''key, 'value) dict -> (''key, 'value) dict

会让你写

Dictionary.exists (Dictionary.insert (3,"c") Dictionary.empty) 3;

实施留作练习。

Answer 2

函数中

fun exists dict key =
    case dict of
        [] => []
      | (k, _ )::rep => if k = key
                        then true
                        else exists rep key

我发现两个问题：

你不能在一个地方 return [] 而在另一个地方 true。
而不是 if P then true else Q，写入 P orelse Q。

您正在使用 :>，这意味着该模块是 opaque，因此您只能访问签名中指定的内容。签名中未提及内部列表表示，因此您不能将 dict 称为列表，即使您可能知道它是如何实现的。这是一个功能。

我可能会为 member 调用 exists，因为 List.exists 是一个高阶谓词，例如List.exists (fn x => x > 5) [3, 6, 9]。您也可以偏离任何标准库命名并说 containsKey 和 containsValue，或类似的东西。

除了 molbdnilo 建议的 insert 函数外，您可能还希望有一个 fromList 函数。

这是重构后的版本（为了简洁省略了评论，但我认为你的评论很好！）：

signature DICTIONARY =
sig
    type (''key, 'value) dict

    val empty: (''key, 'value) dict
    val member: ''key -> (''key, 'value) dict -> bool
    val insert: (''key * 'value) -> (''key, 'value) dict -> (''key, 'value) dict
    val fromList: (''key * 'value) list -> (''key, 'value) dict
end

structure Dictionary :> DICTIONARY =
struct
    type (''key, 'value) dict = (''key * 'value) list

    val empty = []

    fun member key [] = false
      | member key ((key2, _)::dict) =
          key = key2 orelse member key dict

    fun insert (key, value) [] = [(key, value)]
      | insert (key, value) ((key2, value2)::dict) =
          if key = key2
          then (key, value) :: dict
          else (key2, value2) :: insert (key, value) dict

    fun fromList pairs = foldl (fn (pair, dict) => insert pair dict) empty pairs
end

但是由于您正在构建字典模块，因此您需要考虑两件事：

使使用某种二叉树作为内部表示成为可能，要求键可以排序而不是比较是否相等.
因为标准 ML 没有像 ''key 这样的特殊语法来表达可以订购的东西（Haskell 将其概括为 type classes，但标准 ML 只有特殊语法''key)，这是使用 functors 的一个很好的例子，它是高阶模块的名称，也就是参数化模块。

这是您可以填写的示例签名、函子和结构：

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

signature DICT = sig
  type key
  type 'value dict

  val empty: 'value dict
  val member: key -> 'value dict -> bool
  val insert: key * 'value -> 'value dict -> 'value dict
  val fromList: (key * 'value) list -> 'value dict
end

functor Dict (Ord : ORD) :> DICT = struct
  type key = Ord.t
  type 'value dict = (key * 'value) list

  val empty = ...
  fun member _ _ = raise Fail "not implemented"
  fun insert _ _ = raise Fail "not implemented"
  fun fromList _ = raise Fail "not implemented"
end

此时可以将type 'value dict改成使用二叉树，当需要在这个二叉树中决定向左还是向右时，可以这样写：

case Ord.compare (key1, key2) of
     LESS => ...
   | EQUAL => ...
   | GREATER => ...

当你需要一个字典，其中的键是一些特定的 orderable 类型时，你可以使用这个仿函数创建一个模块：

structure IntDict = Dict(struct
                           type t = int
                           val compare = Int.compare
                         end)

structure StringDict = Dict(struct
                              type t = string
                              val compare = String.compare
                            end)

另请参阅 Standard ML functor examples 了解更多示例。

如何在 SML/NJ 中创建和使用我自己的 structure/signature？

How to create and use my own structure/signature in SML/NJ?

functional-programming

sml

smlnj