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

Question

我在学习 Jason Hickey's Introduction to Objective Caml .

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




首先，实现一个dictionary是什么意思作为 function ?我怎么能想象那个？

我们需要吗array或类似的东西？显然，在这个练习中我们不能有数组，因为 array尚未在Chapter 3中引入.但是How do I do it without some storage?
所以我不知道该怎么做，希望得到一些提示和指导。

Answer 1

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

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 的 key 值(value)。 empty function 是一个字典，将所有键映射到 0 . add 函数创建一个闭包，它接受一个参数，一个键。请记住，我们这里对字典的定义是从键到值的函数，所以这个闭包是一个字典。它检查是否 k' (闭包参数)是 = k哪里 k是刚刚添加的key。如果是，则返回新值，否则调用旧字典。

通过关闭链中的下一个字典(函数)，您可以有效地获得一个闭包列表，而不是由 cons 单元链接。

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

编辑:什么是闭包？

闭包是一个函数，它从创建它的作用域中引用变量(名称)。那是什么意思呢？

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

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

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

let add d k v = ...

所以即使在 add 之后已返回一个新函数，该函数仍引用要添加的参数。所以闭包是一个必须被某个外部作用域关闭才能有意义的函数。