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!

Written 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.