SY

Shalom
Yiblet

Higher Kinded Types: Recursion Schemes (part: 2 / 2)

September 1, 2018 | 4 minutes

If you haven't taken a look at the previous article, part 1, go here.

Now that we have higher kinded types, let see if we can find some use for them. The first thing that came to mind was to do some type-level shenanigans.

type Apply a b = a b

This clearly is a type that adds absolutely nothing in terms of value to an existing representation, but it is a good example of what a higher kinded type is. Let's see what happens if we use this on a data-type-level fix point operator.

newtype Fix a = Fix {unfix :: a (Fix a) }

Huh, this look interesting what happens if apply this newtype to a datatype with no explicit recursion.

-- let TreeS be the standard representation of a Tree
data TreeS b = NodeS {leftS :: (TreeS b), elemS :: b, rightS :: (TreeS b)} | EmptyS
-- let Tree be the higher-kinding recursion scheme representation of a tree data type.
data Tree b a = Node {left :: a, elem :: b, right :: a} | Empty
deriving Functor

Notice that in this case, the type

Fix (Tree Int)
is effectively the type of a recursive Tree with
int
elements. However, the fix abstraction gives us more free tooling.

With a

Tree b
we can encode structural folding and unfolding. In folding the key function is the parametric function that takes part of the list and combines it to an output. For our
Tree b
we can characterize this function as
Tree b a -> a
. For example let
a
be an integer which counts the number of nodes the tree has.

countNodes :: Tree b Int -> Int
countNodes tree = case tree of
Node l b r -> l + r + 1
Empty -> 0

We can use this function to derive a function that computes this value for the entire tree!

countAllNodes :: Fix (Tree b) -> Int
countAllNodes tree = countNodes (fmap countAllNodes (unfix tree))

And just like that we've developed an algorithm that will recurse down this tree and count up all the nodes that tree has. We can make

countAllNodes
more generic to take in a higher order function parameter of type
Tree b a -> a
, the formal term for this function is a catamorphism. As a result we call this next function
cata
.

cata :: (Tree b a -> a) -> Fix (Tree b) -> a
cata f tree = f (cata f <$> unfix tree)

A sibling function exists that does the opposite (more precisely, it's its mathematical dual)

ana :: (a -> Tree b a) -> a -> Fix (Tree b)
ana f base = Fix (fmap (ana f) (f base))

ana
is like
unfold
where as
cata
is like
fold
. Together the two functions give us the ability to both quickly construct the tree and to quickly extract some value out of it.

ana
is amazing for generating tree's out of some latent representation. Like for example, making perfectly balanced trees.

perfectlyBalanced :: int -> Fix (Tree Int)
perfectlyBalanced = ana $ \i -> case i of
0 -> Empty
_ -> Node {left = i - 1, elem = i, right = i - 1}

Using

ana
we can it becomes simple to specify a perfectly balanced tree without going through the hassle of specififying how the function recurses.
ana
and
cata
aren't the only type of higher order functions that you can take advantage of when you abstact out folding either. There are many more variants, and many more ways to recurse down and up normal recursive data structures. If you wanna jump down this this rabbit hole, bring some snorkeling gear and an open mind!

Shalom Yiblet
follow @syiblet