在 OCaml 中字典的功能实现中添加功能

Question

我在这个问题中引用了代码：How to implement a dictionary as a function in OCaml?，我在 OCaml 中编写了我的功能字典代码：

type key = string;;
type 'a dict = key -> 'a option;;
let add (d : 'a dict) (k, v) : 'a dict = fun k' -> if k' = k then v else d k';;
let empty () = ... ;;
let find d k = ... ;;

在这段代码中，我想知道的是add函数是如何工作的。变量 k' 是什么意思？当我们使用 fun 关键字时，例如 let sub x = fun y -> x - y;;，fun 旁边的变量表示一个参数。这样对吗？当我想使用我定义的sub函数时，我们可以用

调用该函数

# sub 1 2;;
- : int = -1

和 2 是绑定到 y 的参数，它是 fun 关键字旁边的变量。然而，在上面的字典代码中，add 函数中有变量 k'，紧挨着 fun 关键字，但它不代表任何附加参数。调用 add 函数所需的参数是一个 'a dict 类型变量和一个 (k, v) 类型元组。不需要第三个参数。那么，k' 是什么意思呢？我不知道。

Answer 1

在 OCaml 中，

let sub x y = x - y

是

的shorthand表示法（语法糖）

let sub = fun x -> fun y -> x - y

为了得到它，让我们选择一个更简单的例子，

let succ x = x + 1

是

的较短语法形式

let succ = fun x -> x + 1

表示我们将名称 succ 绑定到函数 fun x -> x + 1，后者是函数字面量。编程语言中的文字是用于定义值的句法符号。例如，对于整数，我们有一组有限的文字 1、2、3 等。对于字符串，我们实际上有一组无限的文字，例如 "hello", "", "etc"。 OCaml 中的函数也是一个值，与整数或字符串相同，因此它具有函数字面量的语法，即

fun <arg> -> <body>

它创建了一个函数，计算出 <body> 的值，其中所有自由出现的 <arg> 都被替换为实际传递的参数。

您可能已经注意到，我们实际上只能在函数字面量中绑定一个参数。事实上，OCaml 中的所有函数都是一元的。您可能已经知道可以定义像 fun x y -> x - y 这样的函数，但这也只是 fun x -> fun y -> x - y 的语法糖。那么后一种表示法是什么意思呢？让我们加上括号来了解这个函数是如何计算的：

 fun x -> (fun y -> x - y)

所以我们可以识别fun x -> <body>部分，其中<body>是一个函数自身，即<body> = fun y -> x - y。这意味着表达式 fun x -> fun y -> x - y 是一个函数，它接受一个参数 x 和 returns 另一个函数，它接受一个参数 y 和 returns x-y。这种定义函数的方式，即，当您拥有一个 return 函数等的函数而不是接受元组的函数时，称为 currying。

现在，当我们对柯里化的想法感到满意并且 OCaml 中的所有函数实际上都是一个参数时，我们可以回到函数字典的原始示例。

添加函数

let add (d : 'a dict) (k, v) : 'a dict = fun k' -> if k' = k then v else d k'

剥离了（不必要的）类型注释

let add d (k, v) = fun k' -> if k' = k then v else d k'

然后以显式柯里化的形式表示，是

let add = fun d -> fun (k, v) -> fun k' -> if k' = k then v else d k'

所以它是一个函数，对于给定的字典 d 产生一个接受一对 (k,v) 和 return 的函数，一个函数对于所有 k' 都是相等的k 将 return d。如果密钥不同，则它将密钥应用于第一个参数 d。让我们更深入地了解

fun k' -> if k' = k then v else d k'

字面意思。我们可以看到变量 d 和 k 在该函数中自由出现，即它们不受参数 k 的约束。当函数从外部作用域（未在模块级别定义）引用变量时，将创建 closure。闭包是一个不透明的对象，它包含一个指向代码 ¹ 的指针（在我们的例子中它是 if k' = k then v else d k' 和指向每个 captured 的指针变量（即，从外部范围获取的每个变量）。在我们的例子中，它（大致）创建了一个包含三个条目的记录，d、k 和代码。经过一些几个小时的调解，不难看出，函数字典只是闭包的单链表，因为 d 是指向闭包的指针，而闭包又包含指向另一个闭包的指针，直到我们到达指向 empty 的指针，无论键是什么 returns None（并且在您的示例中编码不正确，因为它应该期望任何键，而不是类型单元的值).

综上所述，我们现在可以为 add 函数编写简写符号：

let add d k k' = if k' = k then v else d k'

它与任何其他符号具有完全相同的语义（即含义、行为），因为它只是语法糖。

¹⁾为防止混淆，代码本身从不存储在堆内存中。即使你有一个未绑定任何名称的匿名函数，例如 (fun x y -> x + y) 2 3 ，编译器也会发出代码并将其存储在二进制文件的文本部分并为其命名。所以上面的代码将只是对名称错乱的函数的正常调用，例如 call Testing_fun001。回到函数式字典的例子，每个条目都是一个包含三个词的对象，键、数据、指向下一个条目的指针。与关联列表基本相同的底层表示。

Answer 2

关于你的类型定义..

type key = string;;
type 'a dict = key -> 'a option;;

为什么不...

type 'a dict = 'a -> 'a option;;

甚至更好...

type ('a, 'b) dict = 'a -> 'b option;;

在 OCaml 中字典的功能实现中添加功能

Add function in functional implementation of dictionary in OCaml

ocaml