The first thing that we are going to explore are recursive types, that is, a type that contains itself. This cannot be done directly, as the compiler needs to know in advance how much space a type requires. Consider the following struct:

struct Foo {
    bar: i32
}

The compiler will ask itself, How much space does it take to create a Foo? and see that it needs just enough space to hold an i32. And how much does an i32 need? Exactly 32 bits. Now, consider the following:

struct Foo {
    bar: i32,
    baz: Foo,
}

How much space does Foo need? Enough to hold an i32 and a Foo. How much is an i32? 32 bits. And Foo? Enough to hold an i32 and a Foo. And how much does that Foo take? Enough for a Foo, and so on, until the heat death of the universe. Clearly, we don't want to spend that long on compiling. Let's take a look at the solution to our problem:

struct Foo {
    bar: i32,
    baz: Box<Foo>,
}

One last time, how big is Foo? Enough to hold an i32 and a Foo. How big is an i32? 32 bits. How big is a Box<Foo>? Just as big as a box of any other type, namely 64 bit. Every Box will always have the same size, as they are all the same thing, a pointer to some type in the heap. This way, we resolved our problem, as the compiler now knows the exact size of the type at compile time and is happy. And because it is happy, we are happy.

In our code example, we illustrate one possible use case for a recursive type, a naive binary tree implementation [9]. In case you didn't know, a binary tree consists of a clump of data, which is called a node, that can be connected to either zero or two other child nodes. A node that is connected to zero nodes is a leaf. In our example, we build such a tree that will look like this:

We implement it as a struct Node that contains any data and optionally a pair of BoxedNode, which is just an alias for Box<Node>.

The next thing that a Box enables us to do is classic polymorphism how you will recognize it from other languages. For this, we prepare a trait called Animal [37] that has a method to produce a sound(). Its implementor, Dog [42], will produce "Woof!"[45] and the Cat [50] implementor will produce "Meow!" [53]. Our goal is to store both a Dog and a Cat in a Vec of Animal. We can do this by creating a so-called trait object. It is created by a Box of a trait, like in our example in the following line:

let mut zoo: Vec<Box<Animal>> = Vec::new();

This way, we intentionally erase type information from the actual type in the Box. The compiler no longer knows which type is in the Box, only that it implements Animal, which is all that it needs to know. As you can see by running the code, the Rust runtime will still execute the correct functions and give the Dog and the Cat different sounds.

With the same mechanism, we can return a trait object of Iterator[90]:

fn caps_words_iter<'a>(text: &'a str) -> Box<Iterator<Item = String> + 'a> { ... }

This way, we can mix and match iterators inside caps_words_iter() without caring for the exact return type, so long as it implements Iterator, which they all do. Remember that we can't just return Iterator directly without any Box around it, as we cannot return a trait. A trait object, however, is completely fine.

On we go to read_file_as_number()[96]. This method reads a file and returns the content parsed as an i32. This file will not be generated for you, so you will have to either download it from our GitHub repo or manually create a file called number.txt that contains a number, say 777. From the signature, you can gather that this time we are boxing the Error. This lets us mix the error type returned. Indeed, this method does return two different kinds of errors: std::io::Error and std::num::ParseIntError.

The last thing that we are going to look at is how to return closures with create_multiplier()[105]. As all closures implement either Fn, FnOnce, and/or FnMut, we can return a trait object for them. This way, we can create, compose, and change functions at runtime, just like with functional languages.