正则表达式的Ocaml偏导数

Question

我得到了此代码：

type regexp =
  | V                      (* void                      *)
  | E                      (* epsilon                   *)
  | C of char              (* char                      *)
  | U of regexp * regexp   (* a + b                     *)
  | P of regexp * regexp   (* a.b                       *)
  | S of regexp            (* a*                        *)
;;

...
module ReS = Set.Make (struct
  type t = regexp
  let compare = compare
  end)
(* module/type for pairs of sets of regular expressions *)
module RePS = Set.Make (struct
  type t = ReS.t * ReS.t
  let compare = compare
  end)
(*module/type for set of chars *)
module CS = Set.Make(Char)

let ewps = ReS.exists ewp;;
let atmost_epsilons = ReS.for_all atmost_epsilon;;
let infinitys = ReS.exists infinity;;

let rigth_concat s = function
| V -> ReS.empty
| E -> s
| r -> ReS.map (fun e -> P (e,r)) s
;;
let ( *.* ) = rigth_concat;;

(* partial derivative of a regular expression *)
let rec pd a re = function
  | V | E -> ReS.empty
  | C  b when b=a -> ReS.singleton E
  | C  b -> ReS.empty
  | U (r, s) -> ReS.union (pd a r) (pd a s)
  | P (r, s) when ewp a -> ReS.union ((pd a r) *.* s) (pd a s)
  | P (r, s) -> (pd a r) *.* s
  | S r as re -> (pd a r) *.* re
;;
let rec unions f s =
  ReS.fold (fun re acc -> ReS.union (f re) acc ) s ReS.empty
;;
let rec pds a s = unions (pd a) s;;

let rec pdw (sr: ReS.t) = function
  | [] -> sr
  | a::tl -> pds a (pdw sr tl)
;;

我检查了返回值的类型，我认为它们是正确的，但是它返回以下错误，我不确定为什么。

此表达式的类型为regexp-> ReS.t，但表达式为 期望类型为ReS.t

在函数“ pd”中有错误的行中

| U (r, s) -> ReS.union (pd a r) (pd a s)

Answer 1

我相信您的问题是由function提供了隐式参数这一事实引起的。这个表达式：

function None -> 0 | Some x -> x

是具有one参数的函数。因此，在您的情况下，您已定义pd为三个参数。在我看来，您似乎希望它具有两个参数。

您可能可以将function ...更改为match re with。或者，您可以删除显式的re参数，并使用function中隐含的参数。