unfold

Every functional programmer loves fold. fold is universal and expressive. But fold has a secret twin brother named unfold which undoes what fold does. In this post, we will see what unfold is and how it is related to fold.

unfoldr builds a list from a seed value while foldr reduces a list to a summary value.

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

unfoldr takes the element and returns Nothing if it is done producing the list or returns Just (a, b), in which case, a is a prepended to the list and b is used as the next element in a recursive call.

For example, we can define iterate as follows:

iterate f == unfoldr (\x -> Just (x, f x))

Another simple use of unfoldr:

> unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
[10,9,8,7,6,5,4,3,2,1]

As the name suggests, unfold is the categorical dual of fold. (Maybe it should be cofold instead of unfold.) It means we can get the signature of foldr by reversing the arrows of unfoldr, and vice versa.

Let’s try this.

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

Oops! It is not our beloved foldr function whose signature is:

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

Type isomorphisms

But don’t be disappointed! We can show that they represent the same thing by using type isomorphisms:

(a → b → b) → b → ([a] → b)

by a -> b -> c ~= (a, b) -> c

((a, b) → b) → b → ([a] → b)

by a ~= () -> a

((a, b) → b) → (() -> b) → ([a] → b)

by a -> b -> c ~= (a, b) -> c

(((a, b) → b), (() -> b)) → ([a] → b)

by ((a -> c), (b -> c)) ~= Either a b -> c

((Either (a, b) ()) → b) → ([a] → b)

by Either a () ~= Maybe a

(Maybe (a, b) -> b) → ([a] → b)

Now we can clearly see that unfold is the dual of fold. If you want to learn more on the relationship between fold and unfold, see Conal Elliott’s Folds and unfolds all around us.

Implementation

Here’s an implementation of unfoldr.

unfoldr :: (b -> Maybe (a, b)) -> (b -> [a])
unfoldr f b = case f b of
                Just (a, b') -> a : unfoldr f b'
                Nothing -> []

Haskell is notorious for being hard to learn. Pure functions, lazy evaluation, Haskell type system are just start.

To use Haskell effectively, it is necessary to learn the abstract concepts borrowed from the category theory such as Functor, Applicative Functor and Monad. You need to understand these concepts throughly because most of Haskell code is written using these abstract non-sense.

Of course, it is still possible to write IO code and use Maybe, Either and List types without understanding Monad. But then why do you want to learn Haskell anyway? If you avoid learning these concepts, you can’t learn much from Haskell. It would be much beneficial to learn other more practical languages.

Before explaining why you should learn Haskell, let’s ask a question. What’s the essence of programming?

Programming is basically instructing the computer to some labor. For example, “Load the value at memory x into the register, add 1 to it, and store the value back to the memory” is a program.

But a program is not just a sequence of instructions. It is a solution to our real problem. What makes programming interesting is that the problems we solve as a programmer is much bigger in size than simply loading a value from the memory and doing some arithmetic.

So programming is to divide a big problem that can’t be solved at once into many small problems, solve them independently, and compose the resulting small programs into a program that solves the original problem. In other words, the essence of programming is recomposition after decomposition. See Bartosz Milewski’s Category: The Essence of Composition.

Here comes the most important property of programming, which is called composability. We need to solve many complex problems which are similar but not exactly same. If we can compose small reusable programs into a new program which solves the new problem, the productivity of a programmer will be dramatically increased.

The changes of programming paradigm in the history can be explained as our continuous endeavor to enhance the composability. For example, the shift from assembly programming with goto to structure programming emphasizing subroutine and loop was necessary as the problem size increases. We desperately needed a better way to compose programs.

But as the complexity of problem drastically increased again in 80-90s, we needed a new programming paradigm called object-oriented programming. Classes and objects, encapsulation and information hiding were another endeavor to improve the composability of programs.

Now in 2010s, functional programming is gaining attention. The complexity of problems we have today is enormous and we need new tools and concepts to cope with ever increasing complexity. Classes are not enough. We need more composability.

Haskell provides new tools and concepts which can help organize code better. Concepts like Functor, Applicative Functor, Monad, Arrow and Lens all provide new means to compose programs. See Gabriel Gonzalez’s The category design pattern.

In fact, you already know some of these concepts. For example, ES6’s Promise, C#’s null propagation operator, Python’s list comprehension all share the same monadic structure. But you probably never noticed the common structure lying behind these different language features. After you learn Haskell, you will begin to see the common structure you’ve never imagined before.

In summary, the essence of programming is composition. Haskell provides new tools and concepts to compose programs. Learning Haskell improves your code organizational skills and make you prepared to handle more complex problems. Learn you a Haskell for great good!