Folds are a pretty big deal. I’ve written a lot about them in the past. One thing I haven’t covered, however, is their sister: the unfold, or anamorphism.

In Data.List there is the unfoldr function, which has the following type:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

This function can be thought of as a very simple state machine. You pass in the initial b state, and for each iteration you feed the current state into the supplied function. If the result is Nothing, we’re done. Otherwise, we have an a along with a new state b. It should be clear how repeated application can generate a list.

Exercise: Implement unfoldr.

However, viewed under the lens of fixed points, the type signature of unfoldr is a bit deceptive. Recall the definition of ListF:

data ListF a b = NilF | ConsF a b

But this type is actually isomorphic to Maybe (a, b)! This is given by the following isomorphism:

to :: ListF a b -> Maybe (a, b)
to NilF        = Nothing
to (ConsF a b) = Just (a, b)

from :: Maybe (a, b) -> ListF a b
from Nothing = NilF
from (Just (a, b)) = ConsF a b

This means that we can rewrite the type of unfoldr to use ListF a b instead of Maybe (a, b).

unfoldr :: (b -> ListF a b) -> b -> [a]

Now, recalling that [a] ~ Fix (ListF a), we can start to see the true generality of the unfold come out:

unfoldr :: (b -> ListF a b) -> b -> Fix (ListF a)

Of course, as with cata, the only thing we truly need to assume about ListF a is that it is a Functor. So we end up with this new function:

ana :: Functor f => (b -> f b) -> b -> Fix f
ana h = Fix . fmap (ana h) . h

The type signature of ana is different from cata in two ways:

• The f b -> b has been flipped to b -> f b
• b and Fix f have been flipped

This corresponds to the fact that ana and cata are duals in a precise categorical sense that I won’t go into.

Encoding

ana is a very handy function to use any time a list is being built up inductively. But cata seems somehow more special: any value of a data type can be uniquely represented as a fold on the value itself. Is there a similar representation property for unfolds?

For the case of lists, the question is answered (at least somewhat) positively. Recall that when encoding a list as a fold, we “partially apply” the list value and leave everything else free. Here, we will do the opposite: we will supply the builder function and the seed value, but not the list itself. I chose Int for b for reasons that will become clear soon.

type List1 a = (Int -> Maybe (a, Int), Int)

Decoding the list is as easy as simply calling unfold:

decode :: List1 a -> [a]
decode (f, n) = unfoldr f n

But how do we encode an arbitrary list? Well, we can use the Int to describe the length of the list. When it reaches 0, we know that there are no more elements in our list to produce. Given a list encoded in this way, all we have to do to is increment the Int and wrap the current builder function with one that produces the supplied value as our new head.

encode :: [a] -> List1 a
encode []    = (const Nothing, 0)
encode (h:t) = (go, n + 1)
  where (f, n) = encode t
        go x = if x == n + 1
                   then Just (h, n)
                   else f x

Encoding a list and decoding it again will certainly produce the same list. (Exercise: why?) However, if we go in the other direction — that is, decode a list, and then encode it — we could very well end up with a different value than what we had before. encode xs only describes one particular method of encoding xs; there are plenty others. This process can be generalized to other (recursive) data types, but extra data will have to be included proportional to the number of constructors and their arguments.

Conclusion

There’s still one more interesting duality that I’d like to mention. If you have a fold on a data type, e.g. a list, the type signature looks like this, modulo some equivalences:

foldr :: b -> (a -> b -> b) -> [a] -> b
      :: (() -> b) -> (a -> b -> b) -> [a] -> b
      :: (() -> b, a -> b -> b) -> [a] -> b

That is, it takes a product of destructors, a built-up value, and produces a destroyed result. Now, if we think about unfolds the same way, we get:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
        :: (b -> ListF a b) -> b -> [a]

which takes a (function to a) coproduct of constructors, a seed value, and produces a built-up result. I think there’s a more precise way of stating this. Maybe the answer is to use the language of final coalgebras, but I’m not sure.

Exercise: Figure this out for me :)