如何在ADT上定义多态比较?

问题描述 投票:1回答:1

多态compare函数可用于实例化OCaml预定义函子(Map.MakeSet.Make,...)。在这种情况下,我们只需要知道它的行为就像一个订单,但它可能有助于理解它是如何实际定义的。例如,如何确保以下函数正确计算列表的最大值:

let rec max_list = function
| [] -> None
| h::t -> max (Some h) (max_list t)

我首先想到前面定义的构造函数小于后面定义的构造函数。然而,似乎并非如此,因为max Non (Som 2)具有Som 2 : opt值,opttype 'a opt = Non | Some of 'a还是type 'a opt = Some of 'a | Non

为了比较代数数据类型的值,我希望它比较构造函数,然后,如果它们相同,则比较它们的参数。为什么不是真的,如何定义比较?

comparison ocaml algebraic-data-types
1个回答
1
投票

如果你看一下compare函数和前面的比较运算符(目前在https://caml.inria.fr/pub/docs/manual-ocaml-4.08/core.html#sec551)的语言定义,你会发现没有明确保证变量类型的不同构造函数的顺序。它只能保证它代表一个总订单。

如果需要特定订单,则需要定义自己的比较功能。

在当前实现中,没有参数的构造函数(nullary构造函数)被视为小于带参数的构造函数,即使它们出现在定义的后面。在我看来,依赖于此是不明智的,因为语言定义中没有明确的保证。

# type ab = B of int | A;;
type ab = B of int | A
# A < B 2;;
- : bool = true
# type cd = C | D of int;;
type cd = C | D of int
# C < D 2;;
- : bool = true
# type ef = E | F;;
type ef = E | F
# E < F;;
- : bool = true
© www.soinside.com 2019 - 2024. All rights reserved.