具有 1 个构造函数的 SML 多类型二叉树

Question

我正在尝试实现一个二叉树，其中每个节点都可以保存类型为“a”或类型为“b”的信息。简单的解决方案是像这样使用 2 个构造函数：

datatype ('a, 'b) Tree = Lf
                | Br1 of 'a * (('a, 'b) Tree) * (('a, 'b) Tree)
                | Br2 of 'b * (('a, 'b) Tree) * (('a, 'b) Tree);
Br1(100,Lf,Br2("hello",Lf,Lf));
>val it = Br1 (100, Lf, Br2 ("hello", Lf, Lf)): (int, string) Tree;

但是，我想使用 1 个构造函数，因此结果如下：

Br(100,Lf,Br("hello",Lf,Lf));
>val it = Br (100, Lf, Br ("hello", Lf, Lf)): (int, string) Tree;

模式匹配似乎不起作用，returns调用 Br 时出现长类型冲突错误：

datatype ('a, 'b) Tree = Lf
            | Br of 'a * (('a, 'b) Tree) * (('a, 'b) Tree)
            | Br of 'b * (('a, 'b) Tree) * (('a, 'b) Tree);

我觉得它与联合数据类型有关，所以我尝试了以下方法，但是当我尝试这样调用 Br 时，它给出了一个错误：

local
datatype ('a,'b) u = t1 of 'a
                    | t2 of 'b;
in
datatype ('a, 'b) Tree = Lf
                | Br of ('a,'b) u * (('a, 'b) Tree) * (('a, 'b) Tree);               
end;

Br(100,Lf,Br("hello",Lf,Lf));
Elaboration failed: Unbound type "u".

可能语法不对，或者我的想法有误？

Answer 1

a binary tree in which every node can hold information of type 'a or type 'b

虽然您可以使用单个二叉树类型来执行此操作，但我会将其分为两种数据类型：树类型和 "either 'a or 'b type"，因为这两种都是规范数据类型，这意味着它们是被函数式程序员识别。

datatype 'a tree = Leaf | Branch of 'a * 'a tree * 'a tree

datatype ('b, 'c) either = One of 'b | Other of 'c

val someTree = Branch (One 100, Leaf, Branch (Other "hello", Leaf, Leaf))

这棵树的类型是(int, string) either tree。

当给一个值加上前缀 One 时，它接受一个类型 'b 的值，当给一个值加上前缀 Other 时，它接受一个类型 'c 的值。请注意，它们可以在这里命名为 'a 和 'b，但我认为给它们新的变量名称会减少将 'a' 替换为 ('b, 'c) either 时的混淆。

（另请注意，通常此 ('b, 'c) either 类型具有名为 Left 和 Right 的构造函数，但自从 "left" 和 "right"对二叉树也有意义，这可能会增加混淆。树的方向仍然由位置决定，所以第一个'a tree是左子树，第二个'a tree是右子树。)

您可以将两种数据类型组合成一个定义，如下所示：

datatype ('a, 'b) eithertree =
    Leaf
  | BranchA of 'a * ('a, 'b) eithertree * ('a, 'b) eithertree
  | BranchB of 'b * ('a, 'b) eithertree * ('a, 'b) eithertree

val anotherTree = BranchA (100, Leaf, BranchB ("hello", Leaf, Leaf))

一些注意事项：

这两种数据类型是同构的：您可以创建一个将第一个映射到第二个的函数，以及将第二个映射到第一个的反函数。所以你想问问自己，如果它们可以互换，它们有什么优缺点。
类型构造函数现在是 eithertree，因为它结合了两个概念。
之前，tree 类型构造函数只接受一个 'a 类型参数。现在 eithertree 采用 ('a, 'b)，因为在 'a 和 'b 之间进行选择的机制已嵌入到树类型中。
值构造函数稍微简单一些：BranchA 自然假设它的第一个参数是 'a，其中 Branch 必须明确地在 One 前面'a 每次（'b 和 Other 也是如此）。
数据类型定义稍微复杂一点：每个对子树的自引用现在都更加复杂，因为它需要一对类型参数 ('a, 'b) 而不是像首先 'a tree 做到了。我认为，这主要是必须定义数据类型时的一个缺点。这可能是你被卡住的原因。
('a, 'b) eithertree 的可组合性较差：假设您构建了一堆二叉树遍历函数。这些不适用于 ('a, 'b) eithertree，因为它们不是 'a tree。但是 ('a, 'b) either tree 是一个 'a tree 而 'a 是 ('a, 'b) either。所以您可以重用更少的代码。

Answer 2

你们很亲近。

因为你的联合类型是local，你根本不能在('a, 'b) Tree的定义之外使用它。

这个问题很容易解决-让它不是本地的：

datatype ('a,'b) u = t1 of 'a
                   | t2 of 'b;

datatype ('a, 'b) Tree = Lf
                       | Br of ('a,'b) u * (('a, 'b) Tree) * (('a, 'b) Tree);

(u 类型通常非常有用，通常称为 "either"，有时也称为 "variant"。我不知道为什么它不在 SML 基础库中。 )

第二个问题是您需要使用 u 的构造函数来创建 u 的值，就像其他地方一样：

- Br(t1 100,Lf,Br(t2 "hello",Lf,Lf));
val it = Br (t1 100,Lf,Br (t2 #,Lf,Lf)) : (int,string) Tree

无法避免显式构造值。
（int是t1还是t2类型谁都猜不出来，(int, string) u和(string, int) u是不同的类型。）

Answer 3

the constructor for the non leaf nodes should be singular and without added information from the user, like the type of the value he wants to build the tree with. I thought my result example explained it.

我会提供另一个答案，因为现在给出的两个答案在这个约束方面都不令人满意。正如我评论的那样，如果您想要一个采用 int 或 string 的构造函数，您需要 ad-hoc 多态性 而不是 参数多态性 .

这个 OCaml 问题有一些相似之处：Make OCaml function polymorphic for int lists and float lists -- 主要区别在于那个问题需要一个函数，而这个问题需要一个数据类型定义。正如 Jeffrey Scofield 指出的那样（在您的情况下将类型调整为 int 和 string）：

The only common type for int and string is 'a, i.e., any type at all. Since the value can be anything, there are no specific operations you can apply to it. So there's no straightforward way to write the function you want.

但正如我也回答的那样，OCaml 有一个名为 "modular implicits" 的实验性扩展，它允许您编写将模块作为参数的函数，并且在这些模块中，您可以提供一个类型参数，以及一个函数接口在两种或多种类型中是常见的。我不知道标准 ML 有类似的东西。

您的要求可以归类为 heterogenous tree, and in Haskell you'd make that with either of the ExistentialQuantification or GADTs GHC extensions. It is often the case that some of the overloading mechanisms of Haskell have some comparable use in the ML module system, but in the case of GADTs, the best I was able to find is encoding of GADTs in the ML module system using Church numerals，因此这更像是概念验证而非实际解决方案。

具有 1 个构造函数的 SML 多类型二叉树

SML multiple type binary tree with 1 constructor

tree

binary-tree

sml