#structural recursion

(Intro post)

[Update: Mindy made me aware of the concept of Tying the Knot, which allows the construction of cyclical data structures in Haskell. It is not safe to use structural recursion with cyclical data structures, but it remains a useful recursive pattern nonetheless. See Skeleton.hs in the examples section for a practical application which would be difficult without the guarantees provided by structural recursion.]

Introduction

A “recursively defined data type” is a type which references itself in its definition. This is possibly vague, weird, and bad-sounding if you're coming at this from an OOP angle, but it's a very fundamental concept in the Lisps and Schemes of the world. It is this idea which changes recursion from a nasty beastie to a friendly nyancat.

In this post I try to explain structural recursion in a way that is accessible to programmers from all backgrounds. I start by defining a datatype in Haskell and translating this datatype to Python. Next I define a __repr__ method for the datatype (this is like a toString method in Java), and show how structural recursion enables a natural definition of repr in both Haskell and Python.

Recursively defined data type

Here's an example of how you might define a linked list in Haskell:

data List thing = Empty | Element thing (List thing)

You might read that definition as:

A List of things is one of two possibilities. It may be either an Empty or it could be an Element carrying one thing and a whole List of more things.

(Aside: The thing is the type of elements in the list. Lists are homogenous in Haskell for the most part. If this is confusing, try reading the definition aloud while saying Int wherever you see thing.)

Our use of List thing as a type in the second argument to the Element constructor is what makes this a recursively defined data type.

Let's see some examples.

According to our definition, this is a list:

Empty

This is also a list. It has a length of one and contains some sort of Inty number.

Element 4 Empty

This list contains a 3 followed by a 4.

Element 3 (Element 4 Empty)

This may seem foreign. It is a very functional-programmingy way to think about linked-lists, and Haskell might be a foreign syntax for you. Let's explore more in Python.

Recursively defined data type dot py

We need to implement our list as a thing that can be constructed in one of two ways, where both constructors produce something recognizable as being a part of the same type. Looking to the expression problem [1] for guidance hints at the right way to set things up.

First we define a list type. Our two constructors will be members of this type by extending it.

class List(object): def __init__(self): raise NotImplementedError()

The list type is abstract (you can't construct one). It's just there so that we can extend it.

class Empty(List): def __init__(self): pass def __repr__(self): return '{}()'.format(self.__class__.__name__)

The Empty class lets us construct and repr an empty list.

class Element(List): def __init__(self, thing, nxt): assert isinstance(nxt, List), 'nxt argument should be a list' self.thing = thing self.nxt = nxt def __repr__(self): return '{}({}, {})'.format(self.__class__.__name__, repr(self.thing), self.nxt)

The Element class lets us carry one thing and another which must be a subclass of List. It defines __repr__ in terms of these properties.

gist

Now let's see the same examples that we defined above:

An empty list.

Empty()

A list of length one containing an int.

Element(4, Empty())

A list containing 3 followed by 4.

Element(3, Element(4, Empty()))

Recursion that works

>>> repr( Element(3, Element(4, Empty())) ) 'Element(3, Element(4, Empty()))'

Our implementation of Element.__repr__ is recursive. Inside the method we implicitly coerce self.nxt to a string, and Python dispatches to the corresponding __repr__ method on the class of self.nxt. Since self.nxt is restricted by Element.__init__ to a subclass of List, it's probably either an instance of Element or Empty.

In the absence of mutation, it's not possible to put a reference to the whole structure anywhere inside the structure [2]. That means that we'll eventually stop seeing instances of Element, find an instance of Empty, and stop recursing. This recursion is guaranteed Halting™.

Infinite recursion

At this point you may notice that this approach has some problems. You're right. Never write production code like this in Python. Eventually somebody will make a list point to itself and everything will break.

>>> quux = Element(3, Element(4, Empty())) >>> quux.nxt.nxt Empty() >>> quux.nxt.nxt = quux

Now if you were to call repr(quux) you'd see Python attempt to recurse infinitely.

RuntimeError: maximum recursion depth exceeded while calling a Python object

The infinite part of this recursion originated when we mutated the last pointer in our linked list from Empty() to quux. Now the coercion of self.nxt to a string always calls another Element.__repr__.

That mutation of the last pointer inside quux is called a side effect. It introduces a notion of time into our code which didn't previously exist. Before and after the execution of that assignment statement are distinct moments, and the thing we call quux has had its internals changed between those moments.

You wouldn't do this in Haskell because the language intentionally discourages the use of side effects [2,3].

(Aside: Not only does this cause infinite recursion, but it's also a reference cycle, the bane of reference-counting garbage collectors.)

Structural recursion

A recursively defined data type is useful because writing a function to operate on a recursively defined data structure is a mechanical reexpression of the original data definition.

Here's how one might implement repr for List a in Haskell.

repr xs = case xs of Element first rest -> "Element " ++ (show first) ++ " (" ++ (repr rest) ++ ")" Empty -> "Empty"

gist

This function is simply a casewise analysis over the same constructors used in the data definition for List a. Notice how recursion into repr occurs at precisely the same place in our function as List a occurred in the data definition.

Transforming the definition of List to a recursive function over Lists is so easy, you could write a program to do it! *ahem*

Progress

To prevent infinite recursion, structural recursion must always take place on a smaller formulation of the same problem. This is why the first step in the Haskell repr is to break off the current item as first from the rest of the list. Recursion only occurs on the rest. Since the problem always reduces in size, eventually it reaches a base case.

In the Python examples, self.thing is always the current item and self.nxt always represents the rest of the list. There's little chance for a mistake when implementing the recursion because they are already separate names in the class definition.

Combination

Once you've identified the place(s) where recursion will appear in your function definition, an easy way to decide how the recursion should look is to ask yourself this question:

If I've already finished writing this function and have obtained the result for the rest of the structure, how do I combine that result with the current one to make a correct result?

A big part of getting structural recursion right is the recognition that each invocation of your function is responsible for only two things:

Process the current item.

Combine the current item with the result of the rest of the structure.

The examples below generalize a few operations and should help to solidify your notions of structural recursion.

More examples

Child post, chrs (which generalizes to map_)

Child post, len_ (which generalizes to reduce_)

On github, Skeleton.hs defines two recursively defined data structures, Skeleton m a and FrozenSkel m a.

freezSkel maps from Skeleton m a to FrozenSkel m a.

flattenSkel reduces from the tree-like FrozenSkel m a to a list.

HTDP is the text book used in the Northeastern University College of Computer and Information Systems. It contains many examples with excruciating detail about structural recursion (and a few other types of recursion).

Subscripts

[1] Expression problem: http://www.infoq.com/presentations/post-functional-scala-clojure-haskell

[2] Lazy evaluation in Haskell actually allows you to create cyclic data structures, but structural recursion on cyclic data structures is not goung to terminate: http://www.haskell.org/haskellwiki/Tying_the_Knot

[3] Mutation inside pure code is possible in Haskell using unsafePerformIO, but this practice comes with some severe caveats: http://hackage.haskell.org/package/base-4.6.0.1/docs/System-IO-Unsafe.html

Credit

Ralf W'14 noticed two grammar errors and suggested a mention of toString in the intro. Thanks!