A tiny regex engine in OCaml

regex.ml

type regex =
| Phi
| Eps
| Char of char
| Union of regex * regex
| Concat of regex * regex
| Star of regex;;

let star x = Star x;;
let ( !* ) = star;;
let union x y = Union (x, y);;
let (++) = union;;
let concat x y = Concat (x, y);;
let (^.) = concat;;

let partitions s = let n = String.length s in
	List.init (n + 1) (fun i -> String.sub s 0 i, String.sub s i (n - i));;
 
let rec matches regex str = match regex with 
| Eps -> str = "" 
| Phi -> false
| Char c -> String.length str = 1 && str.[0] = c 
| Union (x, y) -> matches x str || matches y str
| Concat (x, y) -> List.exists (fun (a, b) -> matches x a && matches y b) (partitions str)
| Star x -> str = "" || List.exists (fun (a, b) -> a <> "" && matches x a && matches (Star x) b) (partitions str);;

let a = Char 'a';;
let b = Char 'b';;
let re = ((!* a) ^. (!* b)) ++ ((!* b) ^. (!* a));;
let v1 = matches re "aaabbb";;
let v2 = matches re "bbbaaa";;
let v3 = matches re "ababab";;