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

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

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

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

Shalom
Yiblet