Recursion Schemes Explained Using Regular Expressions

Derivatives of Regular Expressions Algorithm

Explaining recursion schemes requires an example. For this, I have chosen the derivative algorithm for regular expressions, which I have covered in a previous article.

For this post, I will include only the implementation code using normal recursion so that we can see how adding recursion schemes will make a difference. Here is the full regular expression matching algorithm using the recursion we are used to.

module Derive
    ( Regex(..), match
    ) where

data Regex = EmptySet
  | EmptyString
  | Character Char
  | Concat Regex Regex
  | ZeroOrMore Regex
  | Or Regex Regex

nullable :: Regex -> Bool
nullable EmptySet = False
nullable EmptyString = True
nullable Character{} = False
nullable (Concat a b) = nullable a && nullable b
nullable ZeroOrMore{} = True
nullable (Or a b) = nullable a || nullable b

deriv :: Regex -> Char -> Regex
deriv EmptyString _ = EmptySet
deriv EmptySet _ = EmptySet
deriv (Character a) c = if a == c
  then EmptyString else EmptySet
deriv (Concat r s) c = if nullable r
  then (deriv r c `Concat` s) `Or` deriv s c
  else deriv r c `Concat` s
deriv (ZeroOrMore r) c =
  deriv r c `Concat` ZeroOrMore r
deriv (Or r s) c =
  deriv r c `Or` deriv s c

match :: Regex -> String -> Bool
match expr string = nullable (foldl deriv expr string)

The derivative or deriv function returns the regular expression left to match, given a character as input. We loop this over the input string using foldl, to get the regular expression that is left to match after we have consumed the whole string. Then we check whether the resulting regular expression matches the empty string using the nullable function, to know whether the regex that has consumed the entire string matched that string.

Technically, foldl already abstracted some recursion, but we are going to take this abstraction to another level with recursion schemes.

A Taste

Before we go too deep, let’s get a taste of where we are going. The nullable function is a perfect catamorphism since it only does bottom-up recursion. Bottom-up recursion is when the result of a function only depends on the results of the recursive function applied to its children and not on any intermediate result passed down in the recursive function. We are going to replace our nullable function in the original implementation above with the following equivalent function:

nullableAlg :: FAlgebra RegexF Bool
nullableAlg EmptySet = False
nullableAlg EmptyString = True
nullableAlg Character{} = False
nullableAlg (Concat a b) = a && b
nullableAlg ZeroOrMore{} = True
nullableAlg (Or a b) = a || b

nullable :: Regex -> Bool
nullable = cata nullableAlg

Notice how the nullableAlg function doesn’t have to do any recursive calls to itself. In this article, we will explain how this is possible as well as:

• what an FAlgebra is

• why there is a new type called RegexF

• how the cata function performs a bottom-up recursion

What the Functor

Our recursion schemes require a place to store intermediate results during our recursion. We need a container for these results. We know a functor is a great container, so we will turn our Regex data type into a functor by parametrising it. This parameter can then store various intermediate results during our recursive algorithms.

We start by renaming Regex to RegexF where the F stands for functor. We parametrise all the recursive Regex fields. Here’s the code:

data RegexF r = EmptySet
  | EmptyString
  | Character Char
  | Concat r r
  | ZeroOrMore r
  | Or r r
  deriving Functor

If you go back and look at the original definition of Regex you will see that we have replaced all the recursive occurrences of Regex with r. We named the parameter r for recursive or result. This r will be used to store boolean results as we do bottom-up recursion for our nullable function using the catamorphism, but more on that soon.

First, we have a problem. We have to choose what parameter to set r to, to get our original Regex back using the definition of RegexF.

• If we make r a Bool, we can only create very small expressions like EmptyString, but others make even less sense: Concat True False.

• If we pick r to be Regex we get RegexF Regex, which will work, but we lose our recursive functor property.

• We can try to choose r to be RegexF, then we get RegexF RegexF, this is close, but now we require another RegexF to be the parameter for the second RegexF, so we get RegexF (RegexF RegexF), but this is a never-ending problem. At some point, we want this recursion to end.

• We can try two levels of RegexF, then we get RegexF (RegexF (RegexF ())), but then we can only represent regular expressions of two levels deep.

We want a functor, but we also don’t want to be limited by a maximum recursion depth.

Fix it, Felix

Fix-It Felix Jr. in jail, where it isn’t very useful to fix things if you want to escape — as seen in Wreck-It Ralph

A fixed point is where a function converges or where the input of a function equals the output. For example: f(x) = x² has a fixed point of 1 since 1² = 1.

We can recreate our equivalent Regex data type using a fixed point:

type Regex = Fix RegexF

How is this Fix RegexF equivalent to our original Regex? To understand this, we need to take a closer look at Fix. Fix is a fixed point data type:

newtype Fix f = Fix (f (Fix f))

It took a long time for me to wrap my head around this, but eventually, my mind reached a fixed point.

But if you take a calm look at each piece, it can make sense:

newtype Fix f = Fix (f (Fix f))

1. The first Fix is the type name.

2. The second Fix is the type constructor name.

3. The third Fix is the type being used.

The Fix type takes one type parameter called f. f is a functor, which means it also takes a type parameter. In this case, the type parameter will be the last Fix f.

If we choose RegexF as our f, our type parameter r will be Fix RegexF, but we know that Fix RegexF is really Fix (RegexF (Fix RegexF)), which we know is really Fix (RegexF (Fix (RegexF (Fix RegexF)))), etc. This is exactly what we wanted. We can now represent regular expressions of any depth. Felix fixed it!

WreckIt Ralph can also unfix our Fix data type, which will be useful in the implementation of the catamorphism function.

wreckit does a pattern match on Fix and returns the value inside:

wreckit :: Fix f -> f (Fix f)
wreckit (Fix x) = x

What the F-Algebra

Now that we have created our functor expression, let’s cover some theory about how we will abstract the recursion.

An algebra consists of the following:

1. The ability to form expressions. For example, the Regex constructors and

2. The ability to evaluate these expressions, for example nullable :: Regex -> Bool

Despite an algebra consisting of two parts, the evaluating function is usually called the algebra:

type Algebra e r = e -> r

This means the nullable function is effectively the NullableAlgebra

type NullableAlgebra = Algebra Regex Bool
nullable :: NullableAlgebra

An F-algebra in Category Theory consists of the following:

1. The ability to form expressions with a carrier type r that are functors, for example RegexF r and

2. The ability to evaluate these expressions RegexF r -> r, for example: nullable :: RegexF Bool -> Bool.

This means the type for an F-Algebra is:

type FAlgebra f r = f r -> r

The nullableAlg function is the NullableAlgebra:

type NullableFAlgebra = FAlgebra RegexF Bool
nullableAlg :: NullableFAlgebra

Catamorphism: Bottom-Up Recursion

How does the cata function abstract away the bottom-up recursion? Here is the whole function:

cata :: Functor f => FAlgebra f r -> Fix f -> r
cata alg = alg . fmap (cata alg) . wreckit

This is very abstract. Let’s make it more specific. To help with readability, let’s first add Elm’s pipe operator to Haskell, which is equivalent to the & operator in Haskell, but it looks more like a Unix pipe and indicates the direction. Sorry, I find this easier to read.

infixl 0 |>
(|>) :: a -> (a -> b) -> b
x |> f = f x

Now, let’s make the cata function implementation more specific to the application of the nullableAlg’s function:

cata :: NullableFAlgebra -> Regex -> Bool
cata nullableAlg regex =
  wreckit regex
  |> fmap (cata nullableAlg)
  |> nullableAlg

As a first step, wreckit will take our Regex and remove the outer Fix:

wreckit :: Regex -> RegexF Regex

Now we have a functor, which means we can fmap over RegexF. The fmap recurses one level down. The function we want to recurse with is the nullable function that is equivalent to cata nullableAlg.

nullable :: Regex -> Bool
nullable = cata nullableAlg

At each level of recursion, we want to call our nullable function. So every time we fmap down a level, we pass down cata nullableAlg to be called at the lower level.

fmap (cata nullableAlg) :: RegexF Regex -> RegexF Bool

As we recurse back up, we return a RegexF Bool, which stores the intermediate results of the nullable calculations at the lower levels. We then have to pass it through a final nullableAlg to get the final Bool result.

nullableAlg :: RegexF Bool -> Bool

This means we can now define the nullableAlg function without any recursion since the cata function will do all the bottom-up recursion for our nullable function:

nullableAlg :: FAlgebra RegexF Bool
nullableAlg EmptySet = False
nullableAlg EmptyString = True
nullableAlg Character{} = False
nullableAlg (Concat a b) = a && b
nullableAlg ZeroOrMore{} = True
nullableAlg (Or a b) = a || b

nullable :: Regex -> Bool
nullable = cata nullableAlg

This was just one example of using a catamorphism, and the catamorphism is limited to simple bottom-up recursion, so let’s learn about one more recursion scheme.

Smart Constructors

Before we check out our next recursion scheme, you might be worried about what the API will look like. How will you explain to users what a fixed point is to your library users? The idea is that we will limit these implementation details to the library's internals. Our API will not expose any of the fixed points. It will not expose the nullableAlg function to the users of this library, only the nullable function. The same goes for the data type constructors. We don’t want to expose Fix outside of our library, so we create smarter constructors that construct the fixed points for the user that we can expose:

emptySet :: Regex
emptySet = Fix EmptySet

emptyString :: Regex
emptyString = Fix EmptyString

character :: Char -> Regex
character c = Fix (Character c)

concat :: Regex -> Regex -> Regex
concat a b = Fix (Concat a b)

zeroOrMore :: Regex -> Regex
zeroOrMore a = Fix (ZeroOrMore a)

or :: Regex -> Regex -> Regex
or a b = Fix (Or a b)

This will also be for our own internal convenience when implementing the deriv function using a paramorphism in the next section.

Paramorphism

If you don’t understand for loops, they are just a paramorphism over a natural number — Josef Svenningsson

Let’s look at the original deriv function again:

deriv :: Regex -> Char -> Regex
deriv EmptyString _ = EmptySet
deriv EmptySet _ = EmptySet
deriv (Character a) c = if a == c
  then EmptyString else EmptySet
deriv (Concat r s) c = if nullable r
  then (deriv r c `Concat` s) `Or` deriv s c
  else deriv r c `Concat` s
deriv (ZeroOrMore r) c =
  deriv r c `Concat` ZeroOrMore r
deriv (Or r s) c =
  deriv r c `Or` deriv s c

The deriv function is not a simple bottom-up recursion, since the Concat the step requires checking if the first expression r is nullable. This is information that is only available on the stack. A paramorphism doesn’t only keep an intermittent result in the functor parameter but also keeps a copy of the original expression so that we can check whether it is nullable. This requires a new Algebra called an RAlgebra:

type RAlgebra f r = f (Fix f, r) -> r

The functor now contains a tuple, where the first parameter is a copy of the original expression and the second is the intermediate result. Our DeriveRAlgebra, will look a little confusing since our intermediate result is of the same type as the copy of the original:

type DeriveRAlgebra = RAlgebra RegexF Regex :: RegexF (Regex, Regex) -> Regex

This RAlgebra will be evaluated by the para function:

para :: (Functor f) => RAlgebra f r -> Fix f -> r
para alg f =
  wreckit f
  |> fmap (\x -> (x, para alg x))
  |> alg

We can make this more specific to the derivAlg function:

para :: DeriveRAlgebra -> Regex -> Regex
para derivAlg regex =
  wreckit regex
  |> fmap (\x -> (x, para derivAlg x))
  |> derivAlg

The only difference from the cata function is the storing of the copy of original Regex, x in the tuple, not just the intermediate result, para derivAlg x.

1. We remove the outer layer of the Fix using wreckit :: Regex -> RegexF Regex.

2. We recurse down one level of the functor using fmap.

3. The function we apply at the lower levels takes a Regex and returns the original Regex as well as the derived Regex : Regex -> (Regex, Regex)

4. The result is in a functor, RegexF (Regex, Regex), which we can then evaluate using: derivAlg c :: RegexF (Regex, Regex) -> Regex to get our final derived Regex.

This means we can now define the derivAlg function without any recursion, since the para function will do all the recursion work for our deriv function:

derivAlg :: Char -> DeriveRAlgebra
derivAlg _ EmptyString = emptySet
derivAlg _ EmptySet = emptySet
derivAlg c (Character a) =
  if a == c
  then emptyString
  else emptySet
derivAlg c (Concat (r, dr) (s, ds)) =
  if nullable r
  then (dr `concat` s) `or` ds
  else dr `concat` s
derivAlg _ (ZeroOrMore (r, dr)) =
  dr `concat` zeroOrMore r
derivAlg _ (Or (_, dr) (_, ds)) =
  dr `or` ds

deriv :: Regex -> Char -> Regex
deriv expr c = para (derivAlg c) expr

You might notice we needed to swap around the input parameters of the derivAlg function to make it work.

The full algorithm

These were just two examples of using recursion schemes, but it is enough to complete our algorithm:

{-# LANGUAGE DeriveFunctor #-}

module FDerive
    ( match
    , emptySet
    , emptyString
    , character
    , concat
    , zeroOrMore
    , or
    ) where

import Prelude hiding (concat, or)

newtype Fix f = Fix (f (Fix f))

wreckit :: Fix f -> f (Fix f)
wreckit (Fix x) = x

type Regex = Fix RegexF

data RegexF r = EmptySet
  | EmptyString
  | Character Char
  | Concat r r
  | ZeroOrMore r
  | Or r r
  deriving Functor

emptySet :: Regex
emptySet = Fix EmptySet

emptyString :: Regex
emptyString = Fix EmptyString

character :: Char -> Regex
character c = Fix (Character c)

concat :: Regex -> Regex -> Regex
concat a b = Fix (Concat a b)

zeroOrMore :: Regex -> Regex
zeroOrMore a = Fix (ZeroOrMore a)

or :: Regex -> Regex -> Regex
or a b = Fix (Or a b)

type FAlgebra f r = f r -> r

cata :: Functor f => FAlgebra f r -> Fix f -> r
cata alg = alg . fmap (cata alg) . wreckit

type NullableFAlgebra = FAlgebra RegexF Bool

nullableAlg :: NullableFAlgebra
nullableAlg EmptySet = False
nullableAlg EmptyString = True
nullableAlg Character{} = False
nullableAlg (Concat a b) = a && b
nullableAlg ZeroOrMore{} = True
nullableAlg (Or a b) = a || b

nullable :: Regex -> Bool
nullable = cata nullableAlg

infixl 0 |>
(|>) :: a -> (a -> b) -> b
x |> f = f x

type RAlgebra f r = f (Fix f, r) -> r

para :: (Functor f) => RAlgebra f r -> Fix f -> r
para alg f =
  wreckit f
  |> fmap (\x -> (x, para alg x))
  |> alg

type DeriveRAlgebra = RAlgebra RegexF Regex

derivAlg :: Char -> DeriveRAlgebra
derivAlg _ EmptyString = emptySet
derivAlg _ EmptySet = emptySet
derivAlg c (Character a) =
  if a == c
  then emptyString
  else emptySet
derivAlg c (Concat (r, dr) (s, ds)) =
  if nullable r
  then (dr `concat` s) `or` ds
  else dr `concat` s
derivAlg _ (ZeroOrMore (r, dr)) =
  dr `concat` zeroOrMore r
derivAlg _ (Or (_, dr) (_, ds)) =
  dr `or` ds

deriv :: Regex -> Char -> Regex
deriv expr c = para (derivAlg c) expr

match :: Regex -> String -> Bool
match expr string = nullable (foldl deriv expr string)

Conclusion

We have only covered two recursion schemes, but there are lots of others:

• Other than para and cata, there is another fold called histo. Histomorphisms preserve the history of all the recursive calculations, which is useful for algorithms that require memoization for efficiency, like Fibonacci.

• Unfolds, include ana, apo and futu. Anamorphism is the Category Theory Dual of the catamorpishm. In Greek, cata means destruction, while ana means building. An anamorphism can recursively build an expression, for example building a list of zeroes with a given length.

• Then there are also refolds: hylo, which is a cata after an ana and chrono, which is a histo and a futu.

I have linked some resources in the References section if you are interested in learning more about recursion schemes so that you can continue your own epic adventures with morph:

what I watched on TV when I was a kid: Morph

Thank you

• Andor Pénzes for proofreading and explaining all the other recursion schemes, especially since I still only understand a few.

References

• Introduction to Recursion Schemes — Patrick Thomson

• Recursion Schemes, Part III: Folds in Context — Patrick Thomson

• Understanding F-Algebras — Bartosz Milewski

• Deriving Modular Recursion Schemes from Tree Automata — Patrick Bahr