OCaml中变体标签的模式匹配

pattern matching of variant tag in OCaml

我有以下 OCaml 替换函数。

let rec subst x a f =                                                                                                                                    
    match f with                                                                                                                                           
    | Var s -> if s = x then a else Var s                                                                                                                 
    | Implies (f1, f2) -> Implies (subst x a f1, subst x a f2)                                                                                            
    | And (f1, f2) -> And (subst x a f1, subst x a f2)                                                                                                     
    | Or (f1, f2) -> Or (subst x a f1, subst x a f2)                                                                                                                                                                                   
    | True | False as e -> e

有些情况几乎相同,我想知道是否有办法以某种方式分解它们。

理想情况下,我正在考虑以下形式的结构:

match f with
| tag (f1, f2) -> tag (subst x a f1, subst x a f2)
| ... 

这将匹配我所有的二进制操作。

另一个用例是 to_string 函数,我们可以在其中:

match f with
| tag (f1, f2) -> print_string ((tag_to_string tag) ^ ...  )
| ... 

我知道这在 OCaml 中是不可能的,但是是否有朝着这个方向发展的模式或语言结构?

不,您不能绑定构造函数。如果你发现自己对此感到厌倦,你可以写mapper/folder 类,这样你就不需要重复自己了。

例如,在我的项目中替换 function 看起来像这样(对于更复杂的语言)

let substitute x y = (object inherit mapper
  method! map_exp z = if Exp.(x = z) then y else z
end)#run

您不能,但您可以创建一个 Binop 构造函数,这样您可以更轻松地使用它。 所以你的类型定义会变成这样:

type binop = Implies | And | Or
type t =
  | Var of string
  | Binop of binop * t * t
  | True | False

那么你的函数可以是:

let rec subst x a f =
  match f with
  | Var s -> if s = x then a else f
  | Binop (b, f1, f2) -> Binop (b, subst x a f1, subst x a f2)
  | True | False -> f

请注意,这会使 Binop 比您的版本多使用一个词,这(在大多数情况下)是为更少的代码行付出的一个很好的代价。

(免责声明:我对 Haskell 比 Ocaml 更熟悉,所以我可能不会以最惯用的方式做事)

我不知道解决这个问题的一般方法(除了某种宏),但我已经学习并发现有用的编码类型如下:

type t =
  | Var of t
  | Implies of t * t
  | And of t * t
  | Or of t * t
  | True
  | False

let apply_t var implies and_t or_t true_t false_t = function
  | Var s -> var s
  | Implies (a, b) -> implies a b
  | And (a, b) -> and_t a b
  | Or (a, b) -> or_t a b
  | True -> true_t
  | False -> false_t

这应该有助于一些函数的定义和类型的抽象使用。在这种情况下,如果您必须定义更多此类函数,只会导致更少的代码。尽管如此,它可能会给你一些想法。有了更多的助手,我们可以看到如何轻松实现像 subst 这样的功能

(* Ocaml constructors behave oddly *)
let impliest (a, b) = Implies (a, b)
let andt (a, b) = And (a, b)
let ort (a, b) = Or (a, b)

let rec subst x a =
  let varf s = if s = x then a else Var s in
  let bin_subst tag f1 f2 = tag (subst x a f1, subst x a f2) in
  apply_t varf (bin_subst impliest) (bin_subst andt) (bin_subst ort) True False

另一种可能更适合某些用例的可能性是将 TrueFalse 编码为单个参数,将值作为 apply_t 函数中的参数。

一种简单的方法是在匹配表达式上方编写一个嵌套函数,但您必须修改变体:

type t =
  | Var of t
  | Implies of (t * t) (* NOTE the parens around the arguments *)
  | And of (t * t)
  | Or of (t * t)
  | True
  | False

let rec subst x a f =
  let g f1 f2 = (subst x a f1, subst x a f2) in
  match f with
  | Var s -> if s = x then a else Var s
  | Implies (f1, f2) -> Implies (g f1 f2)
  | And (f1, f2) -> And (g f1 f2)
  | Or (f1, f2) -> Or (g f1 f2)
  | True | False as e -> e

有一些代码重复,所以它不像 PatJ 那样可扩展,但在某种意义上它也更清晰,因为你只有三个二进制操作。

关于你的标签想法,我不认为有一种方法可以根据参数的数量来绑定构造函数。详情见http://caml.inria.fr/pub/docs/manual-ocaml-400/patterns.html