时间戳

首页 > 解决方案 > 具有 1 个构造函数的 SML 多类型二叉树

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

问题描述

我正在尝试实现一个二叉树，其中每个节点都可以保存'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;

模式匹配似乎不起作用，它在调用 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".

也许语法不正确，或者我的想法是错误的？

标签： treebinary-treesml

解决方案

你很亲密。

由于您的联合类型是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类型通常非常有用，通常称为“要么”，有时称为“变体”。我不知道为什么它不在 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是t1ort2类型；(int, string) u并且(string, int) u是不同的类型。）

推荐阅读