types - 标准 ML 二叉树类型

Question

我正在类里面学习机器学习，并且遇到了一个我一直无法解决的家庭作业问题。我昨天花了一整天的时间进行搜索，但进展甚微，而且我们在类里面也没有讨论过这个问题，所以我希望你们能帮助我。

我们得到:

datatype which = STRING of string | INT of int

第 1 部分。我们被告知需要为包含 which 类型值的二叉树创建另一个名为 whichTree 的数据类型，其中数据仅位于树。

第 2 部分。我们需要创建一个 whichSearch 函数，其类型为 whichTree -> int -> bool 根据 int 是否在树中返回 true 或 false。

这是我到目前为止所拥有的:

datatype which = STRING of string | INT of int;
datatype whichTree = Empty | Node of int*whichTree*whichTree;

val t1 = Node(6, Node(4,Empty,Empty), Node(15, Node(11,Empty,Empty), Node(24,Empty,Empty)));
val t2 = Node(157,Empty,Empty);
val t3 = Node(102,t1,t2);

fun whichSearch (i, Empty) = false
| whichSearch (i, Node(entry, left, right)) =
    if i = entry then true
    else whichSearch (i, left)
    orelse whichSearch (i, right);

我现在面临的问题是:

1. 我的 whichTree 不包含类型 which。我不知道如何解决这个问题。
2. 我应该拥有类型为 whichTree -> int -> bool 的 whichSearch 函数，但它是 int *whichTree -> bool 并且是致力于找出解决问题的方法。我不确定如何解决这个问题，因为我必须在 whichSearch 中为 i 指定一个值来搜索。我正在搜索这个，但任何提示都会很棒。

有人可以帮忙吗？如果是的话谢谢!感谢那些已经回复的人。

Answer 1

根据您提出的建议，我认为我应该指出您正在违反的标准机器学习语言中的一些规则，我希望这些规则能让您更轻松地继续:

• 您引入的每个名称，无论是类型、函数还是变量，都只能表示一个事物(只要它们在程序中处于同一范围内)。

  • 您可以通过首先定义数据类型 which 然后定义同名函数来打破这一点。
  • 您还可以通过首先定义数据类型 whichTree 然后定义同名的另一个数据类型来打破它。
  • 实际上，您还通过引入第一行中已引入的两个新数据类型构造函数(STRING 和 INT)在第三行打破了它。请记住，当您使用这些datatype 声明时，您不仅定义了类型名称，还定义了该类型的构造函数。

• 如果您希望引入带有两个参数的数据类型构造函数(看起来您想在第 3 行执行此操作)，则应在类型之间使用星号 *，而不是在类型之间使用星号 *箭头运算符->。

我也同意 Victor 的观点，你应该从概念上概括地思考二叉树实际上是什么。然后将其转换为标准机器学习。

---

重写问题中的代码后进行编辑:您的新代码要好得多。正如您所指出的，您现在有两个问题:

1. 如何使树成为由 which 值组成的树？好吧，您的树当前是一棵 int 值的树，因此您应该将 int 更改为 which 是不是有意义？但您还声明您的树数据类型应该是“包含类型“which”的值的二叉树，其中数据仅位于树的叶子上”。这与您当前编码的内容不同，您当前编码的内容在每个非叶节点处保留一个int。非叶节点由数据类型声明中的递归情况确定，而叶节点由非递归情况确定。

2. 类型为 (A * B) -> C 的函数(其中 A、B 和 C 是类型)可以重写为类型为 A -> B -> C。两者在标准机器学习中都是有效且可用的，但在函数式编程语言中通常首选第二种形式，因为它允许一种称为柯里化(Currying)的技术，这意味着“部分函数应用”。要进行更改，您基本上以不同的方式编写参数:您编写的是 myFunction a b，而不是 myFunction(a, b)——无论是在定义函数的地方还是在你在哪里使用它。

请注意，我建议您稍后处理第 2 点，首先专注于使数据类型正确并获得有效的搜索功能，然后当您知道它在其他方面是正确的时，您可以更改其类型。