是否有使用数字的 sml 中的 Trie 实现？

Question

sml 中是否有一个 trie 实现，它从输入中获取一个数字，然后将数字分解成它的数字并将它们插入到 trie 中？它是一个已经开发的结构还是有一些我可以使用的现有代码？它有查找功能吗？

Answer 1

快速搜索 "standard ml trie" 会得到以下两个最重要的结果：

github.com/cannam/sml-trie which isn't written in a way that aids educational purposes. The meat of the implementation is in the TrieMapFn functor 参数化键和元素类型，因此您可以将其专门化为某种数字类型。
github.com/jlao/sml-trie 这是一个更容易理解的单个文件。此实现假定键是字符串。您可以 a) 修改它以使用数字来代替——毕竟，它确实 explode 字符串，所以在结构的内部只是 [=13= 的列表]，这也可能是 int 的列表——或 b) 围绕它构建一个包装器，将数字（假设你的数字有一些规范的字符串表示）转换成string 在插入和查找之前。

例如，如果您的号码是 int:

(* Include jlao/sml-trie here. *)

signature NUMBER_DICT =
sig
  type key = int            (* concrete *)
  type 'a entry = key * 'a  (* concrete *)
  type 'a dict              (* abstract *)

  val empty : 'a dict
  val lookup : 'a dict -> key -> 'a option
  val insert : 'a dict * 'a entry -> 'a dict
  val toString : ('a -> string) -> 'a dict -> string
end

structure NumberTrie :> NUMBER_DICT =
struct
  type key = int
  type 'a entry = key * 'a
  type 'a dict = 'a Trie.dict  (* a string-based DICT *)

  val empty = Trie.empty
  fun lookup trie key = Trie.lookup trie (Int.toString key)
  fun insert (trie, (key, value)) = Trie.insert (trie, (Int.toString key, value))
  val toString = Trie.toString
end

由于jlao的DICT有具体的key类型，所以你必须为每一个改变key类型的结构重新签名。这不是那么通用，需要我们将此 Trie 结构转换为一个将键类型作为参数的仿函数。如果您的目标是研究模块系统中的构建函子，这可能更可取。

是否有使用数字的 sml 中的 Trie 实现？

Is there a Trie implementation in sml using numbers?

sml

smlnj