# Time Traveling Recursion Schemes

09 Feb 2016In Practical Recursion
Schemes
I talked about *recursion schemes*, describing them as elegant and useful
patterns for expressing general computation. In that article I introduced a
number of things relevant to working with the
recursion-schemes
package in Haskell.

In particular, I went over:

- factoring the recursion out of recursive types using base functors and a fixed-point wrapper
- the ‘Foldable’ and ‘Unfoldable’ typeclasses corresponding to recursive and corecursive data types, plus their ‘project’ and ‘embed’ functions respectively
- the ‘Base’ type family that maps recursive types to their base functors
- some of the most common and useful recursion schemes:
*cata*,*ana*,*para*, and*hylo*.

In A Tour of Some Useful Recursive Types I went into further detail on ‘Fix’, ‘Free’, and ‘Cofree’ - three higher-kinded recursive types that are useful for encoding programs defined by some underlying instruction set.

I’ve also posted a couple of minor notes - I described the *apo* scheme in
Sorting Slower With Style (as well as how to use
*recursion-schemes* with regular Haskell lists) and chatted about monadic
versions of the various schemes in Monadic Recursion
Schemes.

Here I want to clue up this whole recursion series by briefly talking about two
other recursion schemes - *histo* and *futu* - that work by looking at the past
or future of the recursion respectively.

Here’s a little preamble for the examples to come:

```
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE TypeFamilies #-}
import Control.Comonad.Cofree
import Control.Monad.Free
import Data.Functor.Foldable
```

### Histomorphisms

Histomorphisms are terrifically simple - they just give you access to arbitrary
previously-computed values of the recursion at any given point (its *history*,
hence the namesake). They’re perfectly suited to dynamic programming problems,
or anything where you might need to re-use intermediate computations later.

*Histo* needs a data structure to store the history of the recursion in. The
the natural choice there is ‘Cofree’, which allows one to annotate recursive
types with arbitrary metadata. Brian McKenna wrote a great
article on making
practical use of these kind of annotations awhile back.

But yeah, histomorphisms are very easy to use. Check out the following function that returns all the odd-indexed elements of a list:

```
oddIndices :: [a] -> [a]
oddIndices = histo $ \case
Nil -> []
Cons h (_ :< Nil) -> [h]
Cons h (_ :< Cons _ (t :< _)) -> h:t
```

The value to the left of a ‘:<’ constructor is an *annotation* provided by
‘Cofree’, and the value to right is the (similarly annotated) next step of the
recursion. The annotations at any point are the previously computed values of
the recursion corresponding to that point.

So in the case above, we’re just grabbing some elements from the input list and ignoring others. The algebra is saying:

- if the input list is empty, return an empty list
- if the input list has only one element, return that one-element list
- if the input list has at least two elements, return the list built by cons-ing the first element together with the list computed two steps ago

The list computed two steps ago is available as the annotation on the
constructor two steps down - I’ve matched it as ‘t’ in the last line of the
above example. Like *cata*, *histo* works from the bottom-up.

A function that computes even indices is similar:

```
evenIndices :: [a] -> [a]
evenIndices = histo $ \case
Nil -> []
Cons _ (_ :< Nil) -> []
Cons _ (_ :< Cons h (t :< _)) -> h:t
```

### Futumorphisms

Like histomorphisms, futumorphisms are also simple. They give you access to a particular computed part of the recursion at any given point.

However I’ll concede that the perceived simplicity probably comes with
experience, and there is likely some conceptual weirdness to be found here.
Just as *histo* gives you access to previously-computed values, *futu* gives
you access to values that the recursion will compute in the future.

So yeah, that sounds crazy. But the reality is more mundane, if you’re familiar with the underlying concepts.

For *histo*, the recursion proceeds from the bottom up. At each point, the
part of the recursive type you’re working with is annotated with the value of
the recursion at that point (using ‘Cofree’), so you can always just reach back
and grab it for use in the present.

With *futu*, the recursion proceeds from the top down. At each point, you
construct an expression that can make use of a value to be supplied later.
When the value does become available, you can use it to evaluate the
expression.

A histomorphism makes use of ‘Cofree’ to do its annotation, so it should be no surprise that a futumorphism uses the dual structure - ‘Free’ - to create its expressions. The well-known ‘free monad’ is tremendously useful for working with small embedded languages. I also wrote about ‘Free’ in the same article mentioned previously, so I’ll link it again in case you want to refer to it.

As an example, we’ll use *futu* to implement the same two functions that we did
for *histo*. First, the function that grabs all odd-indexed elements:

```
oddIndicesF :: [a] -> [a]
oddIndicesF = futu coalg where
coalg list = case project list of
Nil -> Nil
Cons x s -> Cons x $ do
return $ case project s of
Nil -> s
Cons _ t -> t
```

The coalgebra is saying the following:

- if the input list is empty, return an empty list
- if the input list has at least one element, construct an expression that will use a value to be supplied later.
- if the supplied value turns out to be empty, return the one-element list.
- if the supplied value turns out to have at least one more element, return the list constructed by skipping it, and using the value from another step in the future.

You can write that function more concisely, and indeed HLint will complain at you for writing it as I’ve done above. But I think this one makes it clear what parts are happening based on values to be supplied in the future. Namely, anything that occurs after ‘do’.

It’s kind of cool - you Enter The Monad™ and can suddenly work with values that don’t exist yet, while treating them as if they do.

Here’s *futu*-implemented ‘evenIndices’ for good measure:

```
evenIndicesF :: [a] -> [a]
evenIndicesF = futu coalg where
coalg list = case project list of
Nil -> Nil
Cons _ s -> case project s of
Nil -> Nil
Cons h t -> Cons h $ return t
```

Sort of a neat feature is that ‘Free’ part of the coalgebra can be written a little cleaner if you have ‘Free’-encoded embedded language terms floating around. Here are a couple of such terms, plus a ‘twiddle’ function that uses them to permute elements of an input list as they’re encountered:

```
nil :: Free (Prim [a]) b
nil = liftF Nil
cons :: a -> b -> Free (Prim [a]) b
cons h t = liftF (Cons h t)
twiddle :: [a] -> [a]
twiddle = futu coalg where
coalg r = case project r of
Nil -> Nil
Cons x l -> case project l of
Nil -> Cons x nil
Cons h t -> Cons h $ cons x t
```

If you’ve been looking to twiddle elements of a recursive type then you’ve found a classy way to do it:

```
> take 20 $ twiddle [1..]
[2,1,4,3,6,5,8,7,10,9,12,11,14,13,16,15,18,17,20,19]
```

Enjoy! You can find the code from this article in this gist.