在 SML 中使用二进制映射数据结构的问题

Question

我想创建一个 有序映射，其中包含 SML 中的多个节点。到目前为止，我发现的所有内容都存在于此处：https://www.smlnj.org/doc/smlnj-lib/Manual/binary-map-fn.html。所以，我正在尝试这样的事情：

structure S = BinaryMapFn(struct
    type ord_key = int
    val compare = Int.compare
  end);

然后，我尝试插入例如 2 个节点，值分别为 0 和键值 1 和 2：

S.insert(S.empty,1,0);
S.insert(S.empty,2,0);

输出：val it = T {cnt=1,key=2,left=E,right=E,value=0} : int S.map

S.numItems(it);

输出：val it = 1 : int

因此，我根据 numItems 的输出假设它创建了 2 个二进制映射，每个映射有 1 个节点，而不是一个。我很确定我遗漏了一些东西，但是没有足够的 material 和与该结构相关的示例。

Answer 1

要看的是 insert function, as well as empty in the signature ORD_MAP BinaryMapFn 符合的类型。

val empty : 'a map 
val insert : ('a map * Key.ord_key * 'a) -> 'a map

因此，insert 采用 (fromMap, key, x) 和 returns 一个新地图，其中包含 fromMap 的元素，并添加了 x/key 作为以某种方式处理重复的键。

要获得包含 2 个元素的映射，而不是在两次调用中都使用 S.empty，您需要将第一次调用的 return 值作为参数传递给第二次调用。

note: 值得注意的是，smlnj-lib 文档非常古老，并且过时了，但我不知道更新的 link，所以最好查阅来源。

Problem with the use of Binary Map Data Structure in SML