OCaml正则表达式偏导代码报错：类型不匹配问题求助

Let's break down the type error you're seeing and fix it step by step.

Root Cause of the Type Mismatch #

Your pd function's definition has a parameter ordering issue that's causing its type to diverge from what you expect:

let rec pd a re = function 
(* ... pattern matches ... *)

Here, function is an anonymous function that expects an additional regexp argument. But you've already passed re as a parameter to pd, which means the function's type ends up being:

char -> regexp -> regexp -> ReS.t

Instead of your intended:

char -> regexp -> ReS.t

When you call pd a r in the U (r, s) case, you're only supplying the first two arguments—this returns a function waiting for a third regexp parameter, not the ReS.t set that ReS.union expects. That's exactly why you get the error: "This expression has type regexp -> ReS.t but an expression was expected of type ReS.t".

Fix 1: Remove the Redundant re Parameter #

Simplify the function to use function directly for the regexp pattern matching, keeping a as the first parameter:

let rec pd a = 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 r -> ReS.union ((pd a r) *.* s) (pd a s)
| P (r, s) -> (pd a r) *.* s
| S r as re -> (pd a r) *.* re ;;

Fix 2: Use match re with Instead of function #

If you prefer to keep the re parameter explicit, replace function with a match expression on re:

let rec pd a re =
match re with
| 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 r -> ReS.union ((pd a r) *.* s) (pd a s)
| P (r, s) -> (pd a r) *.* s
| S r as re -> (pd a r) *.* re ;;

Bonus: Fix a Likely Typo #

I noticed a potential mistake in your P (r, s) case: you wrote ewp a, but a is a char, and ewp (which I assume checks if a regexp matches epsilon) should take a regexp argument. This should almost certainly be ewp r to check if the left-hand side of the concatenation can match the empty string—this is a core part of the partial derivative rule for concatenated regexps.

内容的提问来源于stack exchange，提问作者manuel