OCaml中variant标签的模式匹配

Question

我有以下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中是不可能的，但有没有一种模式或语言结构朝着这个方向发展？

Answer 1

您不能，但您可以创建一个更容易使用的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比您的版本多使用一个单词，这（在大多数情况下）对于减少代码行来说是一个不错的代价。

Answer 2

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

例如，在矿山项目中，替换函数看起来像这样（对于更复杂的语言）

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

Answer 3

（免责声明：我对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

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

Answer 4

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

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