# Promorphisms, Pre and Post

26 Nov 2016To the.. uh, ‘layperson’, pre- and postpromorphisms are probably well into the WTF category of recursion schemes. This is a mistake - they’re simple and useful, and I’m going to try and convince you of this in short order.

Preliminaries:

```
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE LambdaCase #-}
import Data.Functor.Foldable
import Prelude hiding (sum)
```

For simplicity, let’s take a couple of standard interpreters on lists. We’ll define ‘sumAlg’ as an interpreter for adding up list contents and ‘lenAlg’ for just counting the number of elements present:

```
sumAlg :: Num a => ListF a a -> a
sumAlg = \case
Cons h t -> h + t
Nil -> 0
lenAlg :: ListF a Int -> Int
lenAlg = \case
Cons h t -> 1 + t
Nil -> 0
```

Easy-peasy. We can use cata to make these things useful:

```
sum :: Num a => [a] -> a
sum = cata sumAlg
len :: [a] -> Int
len = cata lenAlg
```

Nothing new there; ‘sum [1..10]’ will give you 55 and ‘len [1..10]’ will give you 10.

An interesting twist is to consider only *small* elements in some sense; say,
we only want to add or count elements that are less than or equal to 10, and
ignore any others.

We could rewrite the previous interpreters, manually checking for the condition we’re interested in and handling it accordingly:

```
smallSumAlg :: (Ord a, Num a) => ListF a a -> a
smallSumAlg = \case
Cons h t ->
if h <= 10
then h + t
else 0
Nil -> 0
smallLenAlg :: (Ord a, Num a) => ListF a Int -> Int
smallLenAlg = \case
Cons h t ->
if h <= 10
then 1 + t
else 0
Nil -> 0
```

And you get ‘smallSum’ and ‘smallLen’ by using ‘cata’ on them respectively. They work like you’d expect - ‘smallLen [1, 5, 20]’ ignores the 20 and just returns 2, for example.

You can do better though. Enter the prepromorphism.

Instead of writing additional special-case interpreters for the ‘small’ case,
consider the following *natural transformation* on the list base functor. It
maps the list base functor to itself, without needing to inspect the carrier
type:

```
small :: (Ord a, Num a) => ListF a b -> ListF a b
small Nil = Nil
small term@(Cons h t)
| h <= 10 = term
| otherwise = Nil
```

A *prepromorphism* is a ‘cata’-like recursion scheme that proceeds by first
applying a natural transformation before interpreting via a supplied algebra.
That’s.. surprisingly simple. Here are ‘smallSum’ and ‘smallLen’, defined
without needing to clumsily create new special-case algebras:

```
smallSum :: (Ord a, Num a) => [a] -> a
smallSum = prepro small sumAlg
smallLen :: (Ord a, Num a) => [a] -> Int
smallLen = prepro small lenAlg
```

They work great:

```
> smallSum [1..100]
55
> smallLen [1..100]
10
```

In pseudo category-theoretic notation you visualize how a prepromorphism works via the following commutative diagram:

The only difference, when compared to a standard catamorphism, is the presence of the natural transformation applied via the looping arrow in the top left. The natural transformation ‘h’ has type ‘forall r. Base t r -> Base t r’, and ‘embed’ has type ‘Base t t -> t’, so their composition gets you exactly the type you need for an algebra, which is then the input to ‘cata’ there. Mapping the catamorphism over the type ‘Base t t’ brings it right back to ‘Base t t’.

A *postpromorphism* is dual to a prepromorphism. It’s ‘ana’-like; proceed with
your corecursive production, applying natural transformations as you go.

Here’s a streaming coalgebra:

```
streamCoalg :: Enum a => a -> ListF a a
streamCoalg n = Cons n (succ n)
```

A normal anamorphism would just send this thing shooting off into infinity, but we can use the existing ‘small’ natural transformation to cap it at 10:

```
smallStream :: (Ord a, Num a, Enum a) => a -> [a]
smallStream = postpro small streamCoalg
```

You get what you might expect:

```
> smallStream 3
[3,4,5,6,7,8,9,10]
```

And similarly, you can visualize a postpromorphism like so:

In this case the natural transformation is applied *after* mapping the
postpromorphism over the base functor (hence the ‘post’ namesake).