functional-programming - 如何在 OCaml 中将字典实现为函数？

Question

我正在学习Jason Hickey 的 Objective Caml 简介。

---

这是一个我没有任何线索的练习

---

首先，将 a 实现dictionary为 a 是什么意思function？我怎么能想象出来？

我们需要任何array或类似的东西吗？显然，在这个练习中我们不能有数组，因为array还没有在Chapter 3. 但How do I do it without some storage?

所以我不知道该怎么做，我希望得到一些提示和指导。

Answer 1

我认为这个练习的目的是让你使用闭包。例如，考虑文件中的以下一对 OCaml 函数fun-dict.ml：

let empty (_ : string) : int = 0
let add d k v = fun k' -> if k = k' then v else d k'

然后在 OCaml 提示符下，您可以执行以下操作：

# #use "fun-dict.ml";;
val empty : string -> int = 
val add : ('a -> 'b) -> 'a -> 'b -> 'a -> 'b = 
# let d = add empty "foo" 10;;
val d : string -> int = 
# d "bar";;  (* Since our dictionary is a function we simply call with a
                  string to look up a value *)
- : int = 0   (* We never added "bar" so we get 0 *)
# d "foo";;
- : int = 10  (* We added "foo" -> 10 *)

在这个例子中，字典是一个值string键的int函数。该empty函数是将所有键映射到的字典0。add 函数创建一个闭包，它接受一个参数，一个键。请记住，我们在这里对字典的定义是从键到值的函数，所以这个闭包是一个字典。它检查k'（闭包参数）是否= k是k刚刚添加的键。如果是，则返回新值，否则调用旧字典。

通过关闭链中的下一个字典（函数），您有效地拥有了一个闭包列表，这些闭包不是由 cons 单元链接的。

额外的练习，你将如何从这个字典中删除一个键？

---

编辑：什么是闭包？

闭包是一个函数，它从创建它的范围内引用变量（名称）。那是什么意思呢？

考虑我们的add功能。它返回一个函数

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

如果您只查看该函数，则未定义三个名称，d,k和v. 要弄清楚它们是什么，我们必须查看封闭范围，即add. 我们在哪里找到

let add d k v = ...

因此，即使在add返回一个新函数之后，该函数仍会引用要添加的参数。所以闭包是一个必须被一些外部范围封闭才能有意义的函数。

Answer 2

在 OCaml 中，您可以使用实际函数来表示字典。非 FP 语言通常不支持将函数作为一等对象，所以如果你习惯了它们，一开始你可能会很难这样想。

字典是一个映射，它是一个函数。想象一下，你有一个函数d，它接受一个字符串并返回一个数字。它为不同的字符串返回不同的数字，但对于相同的字符串总是返回相同的数字。这是一本字典。字符串是您正在查找的内容，而您返回的数字是字典中的相关条目。

您不需要数组（或列表）。您的add函数可以构造一个无需任何（显式）数据结构即可执行必要操作的函数。请注意，该add函数接受一个字典（一个函数）并返回一个字典（一个新函数）。

为了开始考虑高阶函数，这里有一个例子。该函数bump接受一个函数 ( f: int -> int) 和一个 int ( k: int)。它返回一个新函数，该函数返回的值k大于f相同输入返回的值。

let bump f k = fun n -> k + f n

（重点是bump， like add，接受一个函数和一些数据，并根据这些值返回一个新函数。）

Answer 3

我认为可能值得补充一点，OCaml 中的函数不仅仅是代码片段（与 C、C++、Java 等不同）。在那些非函数式语言中，函数没有任何与之关联的状态，谈论这样的事情有点荒谬。但是函数式语言中的函数并非如此，您应该开始将它们视为一种对象；一种奇怪的物体，是的。

那么我们如何“制造”这些物体呢？让我们以杰弗里为例：

let bump f k = 
  fun n ->
    k + f n

现在bump实际上做了什么？它可能会帮助您将其bump视为您可能已经熟悉的构造函数。它构建什么？它构造了一个函数对象（这里说的很丢脸）。那么生成的对象有什么状态呢？它有两个实例变量（有点），它们是f和k。这两个实例变量在您调用时绑定到生成的函数对象bump f k。您可以看到返回的函数对象：

fun n ->
  k + f n

利用这些实例变量f并k在它的主体中。一旦这个函数对象被返回，你只能调用它，你没有其他方法可以访问f或k（所以这是封装）。

使用术语function-object非常少见，它们仅称为函数，但您必须记住它们也可以“包围”状态。这些函数对象（也称为闭包）与面向对象编程语言中的“真实”对象相距不远，可以在这里找到一个非常有趣的讨论。

Answer 4

我也在努力解决这个问题。这是我的解决方案，它适用于教科书中列出的案例......

空字典只返回 0：

let empty (k:string) = 0

Find 在键上调用字典的函数。这个函数很简单：

let find (d: string -> int) k = d k

Add 扩展了字典的功能以具有另一个条件分支。我们返回一个带有键 k' 的新字典，并将其与 k（我们需要添加的键）进行匹配。如果匹配，我们返回 v（对应的值）。如果不匹配，我们返回旧的（较小的）字典：

let add (d: string -> int) k v =
    fun k' ->
        if k' = k then
                v
            else
                d k'

您可以更改添加以具有删除功能。另外，我添加了一个条件来确保我们不会删除不存在的密钥。这只是为了练习。无论如何，字典的这种实现很糟糕：

let remove (d: string -> int) k =
    if find d k = 0 then
        d
    else
        fun k' ->
            if k' = k then
                    0
                else
                    d k'

我对术语不太了解，因为我还在学习函数式编程。所以，请随时纠正我。