Today, we’re going to implement applicative regular expressions and parsers (in the style of the regex-applicative library) using free structures!
Free structures are some of my favorite tools in Haskell, and I’ve actually written a few posts about them before, including this one using free groups, this one on a free monad variation, and this one on a “free” applicative on a monoid.
Regular expressions (and parsers) are ubiquitous in computer science and programming, and I hope that demonstrating that they are pretty straightforward to implement using free structures will help you see the value in free structures without getting too bogged down in the details!
All of the code in this post is available online as a “stack executable”. When you run it (
./regexp.hs), you’ll load up a ghci session with all of the definitions in scope, so you can play around with the functions and types :)
This post should be accessible to late beginner or early intermediate Haskell users, and requires some basic familiarity with pattern matching, algebraic data types, and abstractions like
Functor, and do notation.