Dev: Box with recursive data structure

Keywords: box, value types, recursive, type-parameterized

Note: This code is written in Swift 1.2 and not yet validated in Swift 2.0

Despite that value types in general (and enum/struct in particular) bring a lot of advantages, there are several limitations remaining. A typical example is that:

- [Fact 1] Both enum and struct do not support recursive data structure
- [Fact 2] Enum with a type-parameterized case is not allowed

And Box is a micro framework to deal with the painful facts above.


First of all, lets find out the reasons for fact 1 and fact 2. We shall begin with an example: implementing a very familiar data struct: “LIST”.

A list could consist of a head and a tail, which is also a list. A list could be nothing as well.

Unfortunately, this code throws a compiler error. In fact, when XCode allocates memory for List<Int> — for example, it couldn’t estimate how much is enough for Cons(Int, List<Int>) because it does not yet figure out the memory capacity for List<Int> in Cons(Int, List<Int>).

Secondly, it does not accept a type-parameterized associated value: Cons(T, List<T>). ← For this, I still don’t know why.

How to overcome?

Luckily, Box is coming for the rescue. The idea is very simple: make it non-recursive, non-type-paramaterized by using another data structure. The new data structure’s responsibility is wrapping the value in a box. And when you need the value, just unwrap the box.

By this, List<T> is not recursive anymore. But of course, it’s still logically a recursion :D. The compiler won’t complain about the memory allocation problem because it can estimate how much memory a box takes.

Other examples

If you use ReactiveCocoa 3.0 (RAC 3.0), you would see Box as a submodule of it. In fact, RAC 3.0 includes another submodule called “Result”. This micro framework also use Box, too.

Now you can define your own recursive data structure using this trick.

The full demonstration can be found at:

Have fun!