Spaghetti Code and Meatballs

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

September 01, 2018

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 YibletWritten by Shalom Yiblet, a Senior at Carnegie Mellon University. He studies Computer Science with interests in Machine Learning and Programming Languages. He is a Teacher's Assistant for Compilers.