Cook Computing

Functional style regex engine in F#

June 8, 2009 Written by Charles Cook

Nick Palladinos has done a follow-up to my post Functional Style Regex Engine in C# Revisited. In his post Functional style regex engine in F# he presents just that, an F# version of my C# code:


let char c (s : string) = seq { if s.Length > 0 && s.[0] = c then yield s.Substring(1) }

let (=>) l r s = seq { for sl in l s do for sr in r sl -> sr }

let (<|>) l r s = seq { yield! l s; yield! r s }

let rec (<*>) e s = seq { yield s; yield! (e => (<*>) e) s }

let (<+>) e = e => (<*>) e

// example c(a|d)+r
let pattern = char 'c' => (<+>) (char 'a' <|> char 'd') => char 'r'

An interesting difference to my C# version is the use of custom operators, particularly the => and <|> infix operators, which make for a much nicer syntax. Compare the definition of the function pattern above to this:


Rgx.Expr e = Rgx.Seq(Rgx.Char('c'), 
               Rgx.Seq(Rgx.Plus(Rgx.Alt(Rgx.Char('a'), Rgx.Char('d'))), 
                 Rgx.Char('r')));

It's also nice to be able to define functions without having to put them in a class.