如何在OCaml中实现字典作为函数？

Question

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

---

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

---

首先,这是什么意思实现dictionary的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采用function(f: int -> int)和int(k: int).它返回一个新函数,该函数返回的值k大于f为同一输入返回的值.

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

(该点是bump,像add,需要一个功能和一些数据,并返回基于这些值的新的功能.)

Answer 3

我认为可能值得补充的是,OCaml中的函数不仅仅是代码片段(与C,C++,Java等不同).在那些非函数式语言中,函数没有与它们相关的任何状态,谈论这样的事情会有点荒谬.但是功能语言中的函数不是这种情况,你应该开始将它们视为一种对象 ; 一种奇怪的物体,是的.

那么我们如何"制造"这些物体呢？让我们以Jeffrey为例:

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非常罕见,它们只被称为函数,但你必须记住它们也可以"封闭"状态.这些函数对象(也称为闭包)与面向对象编程语言中的"真实"对象相距甚远,这里可以找到一个非常有趣的讨论.