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)
;;

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

This expression has type regexp -> ReS.t but an expression was expected of type ReS.t

在函数"pd"中有错误的行

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

Answer 1

我认为您的问题是由于 function 提供了一个隐式参数。这个表达式：

function None -> 0 | Some x -> x

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

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

中隐含的参数

Ocaml-正则表达式的偏导数

Ocaml- partial derivative of a regular expression

algorithm

ocaml

types