如何将函数放在 Ocaml 的集合中?

How can I place functions in a set in Ocaml?

我想制作一个包含函数的 Set 模块。但是似乎没有办法比较 Set 需要的功能。这个看起来很明显的东西编译:

module Action = struct
  type t = unit -> unit
  let compare : t -> t -> int = Stdlib.compare
end
module Actions = Set.Make(Action)

但如果我尝试使用它:

Fatal error: exception Invalid_argument("compare: functional value")

我只是想比较函数是同一个对象,我不想做一些愚蠢的事情,比如比较它们的行为是否相同。

我应该在这里使用 Obj 模块中的东西吗?

Stdlib.compare的语义是任意深入对象内部,看看它们的子部分如何比较。正如您所指出的,这对函数实际上不起作用。所以 OCaml 不允许 compare 应用于函数。

即使您愿意使用物理相等性,也没有真正有用的顺序可以应用于函数。函数值是不可变的,并且可以通过运行时系统进行物理复制或移动,至少在理论上是这样。

由于顺序必然是任意的,您可以通过自己的任意顺序获得相同的效果:将函数与一个 int 值配对,该值在您创建新对时单调递增。

为您的操作添加标识,例如,您可以按名称比较操作,

module Action = struct 

  type t = {
    name : string;
    func : (unit -> unit);
  }

  let compare x y = String.compare x.name y.name
 end

您还应该确保所有操作都具有不同的名称,例如通过引入一个全局哈希 table 来记录所有已创建的操作。通过添加适当的签名确保操作仅通过 Action 模块创建 table。

OCaml Stdlib compare 文档说明 ...

val compare : 'a -> 'a -> int

compare x y returns 0 if x is equal to y, a negative integer if x is less than y, and a positive integer if x is greater than y. The ordering implemented by compare is compatible with the comparison predicates =, < and > defined above, with one difference on the treatment of the float value nan. Namely, the comparison predicates treat nan as different from any other float value, including itself; while compare treats nan as equal to itself and less than any other float value. This treatment of nan ensures that compare defines a total ordering relation.

compare applied to functional values may raise Invalid_argument. compare applied to cyclic structures may not terminate.

The compare function can be used as the comparison function required by the Set.Make and Map.Make functors, as well as the List.sort and Array.sort functions.

现在我们在 OCaml 中有两个相等的概念,即...

  1. Structural Equality:用运算符=表示,类型为
# (=);;
- : 'a -> 'a -> bool = <fun>
  1. Physical Equality:用运算符==表示,类型为
# (==);;
- : 'a -> 'a -> bool = <fun>

我们可以看到,两者的类型是一样的,但是当function value作为参数时,两者的function application是不同的。

Structural Equality 不保留函数值,但 Physical Equality 可能。 试图比较(如 =) 和 function values 抛出。正如 Stdlib.compare 的文档中所述,它使用 structural equality.


插图:具有函数值的结构相等性

# let f x = x;;
val f : 'a -> 'a = <fun>
# let g x = x;;
val g : 'a -> 'a = <fun>
# f = g;;
Exception: Invalid_argument "compare: functional value".
# g = f;;
Exception: Invalid_argument "compare: functional value".

插图:具有函数值的物理相等性

# let f x = x;;
val f : 'a -> 'a = <fun>
# let g x = x;;
val g : 'a -> 'a = <fun>
# f == g;;
- : bool = false
# f == f;;
- : bool = true
# g == g;;
- : bool = true
# g == f;;
- : bool = false
# let h x y = x + y;;
val h : int -> int -> int = <fun>
# h == f;;
Error: This expression has type int -> int
       but an expression was expected of type int -> int -> int
       Type int is not compatible with type int -> int

简而言之,我认为我们不能将 Stdlib.compareSet.Makefunction values 一起使用。

所以...

  1. 或者,如果我们必须继续使用 Stdlib.compare,我们将不得不将 Action 模块中的 type t 保留为可以应用 structural equality 的东西。 =108=]
  2. 或者,实现你自己的 compare,这样它就可以用那些 function values 作为参数做一些事情,同时满足 [=62] 要求的 val compare : t -> t -> int 的函数契约=] 模块类型。


WYSIWYG => WHAT YOU SHOW IS WHAT YOU GET