标准 ML：二叉搜索树中的查找函数

Question

我正在学习 Ullman 的《机器学习编程基础》。他在 ch 中介绍了 BST 的数据类型。 6个如下：

datatype 'label btree = 
    Empty |
    Node of 'label * 'label btree * 'label btree;

然后他定义了一个查找函数来判断具有给定标签的节点是否存在于 BST 中：

fun lookup lt Empty x = false
    | lookup lt (Node(y, left, right)) x =
        if lt(x, y) then lookup lt left x
        else if lt(y, x) then lookup lt right x
        else true;

ML 告诉我们该函数的类型为：

val lookup = fn : ('a * 'a -> bool) -> 'a btree -> 'a -> bool

1) 我在解析上述内容时遇到问题。我从右边知道“->”关联，但我无法弄清楚如何做到这一点。光看上面的你怎么知道怎么做？

val lookup = fn : ('a * 'a -> bool) -> ('a btree) -> ('a) -> (bool)

2) 不过我很困惑，因为我认为柯里化函数创建了一个函数链，每个后续参数 return 另一个函数。但是根据上面 ML 给我的类型，它看起来并没有被柯里化。知道这里发生了什么吗？

感谢您的帮助，克莱曼

Answer 1

类型val lookup = fn : ('a * 'a -> bool) -> 'a btree -> 'a -> bool告诉我们它接受类型('a * 'a -> bool)的参数和returns类型'a btree -> 'a -> bool的函数。然后这个函数接受类型 'a tree 和 returns 类型的函数 'a -> bool，然后接受类型 'a 和 returns 的参数 bool。所以，是的，lookup 函数被柯里化了。然而，第一个参数（也是一个函数）并没有柯里化，因为它有两个参数，包裹在一对中。通常，您可以采用柯里化函数（即接受参数和 returns 函数的函数）并通过以下方式将其转换为非柯里化函数：

假设您有以下功能

fun f e1 e2 e3 ... = e

类型

'a -> 'b -> 'c -> ... -> 'res

我们可以通过将所有输入包装在一个元组中来取消这个函数，例如

fun f(e1, e2, e3, ...) = e

然后将具有类型

'a * 'b * 'c * ... -> 'res

标准 ML：二叉搜索树中的查找函数

Standard ML: Lookup Function in Binary Search Tree

functional-programming

sml

currying