OCaml中变体标签的模式匹配

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

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

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

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

Answer 2

您不能，但您可以创建一个 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 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

OCaml中变体标签的模式匹配

pattern matching of variant tag in OCaml

design-patterns

pattern-matching

ocaml

variant