Recursive Enumerations in Swift

Question

I'm learning Swift 2 (and C, but also not for long) for not too long and I came to a point where I struggle a lot with recursive enumerations.

It seems that I need to put indirect before the enum if it is recursive. Then I have the first case which has Int between the parentheses because later in the switch it returns an Integer, is that right?

Now comes the first problem with the second case Addition. There I have to put ArithmeticExpression between the parentheses. I tried putting Int there but it gave me an error that is has to be an ArithmeticExpression instead of an Int. My question is why? I can't imagine anything what that is about. Why can't I just put two Ints there?

The next problem is about ArithmeticExpression again. In the func solution it goes in an value called expression which is of the type ArithmeticExpression, is that correct? The rest is, at least for now, completely clear. If anyone could explain that to me in an easy way, that'd be great.

Here is the full code:

indirect enum ArithmeticExpression {
    case Number(Int)
    case Addition(ArithmeticExpression, ArithmeticExpression)
}

func solution(expression: ArithmeticExpression) -> Int {
    switch expression {
    case .Number(let value1):
        return value1;
    case . Addition(let value1, let value2):
        return solution(value1)+solution(value2);
    }
}

var ten = ArithmeticExpression.Number(10);
var twenty = ArithmeticExpression.Number(20);
var sum = ArithmeticExpression.Addition(ten, twenty);
var endSolution = solution(sum);
print(endSolution);

Craggy

Answer 1

The reason the Addition case takes two ArithmeticExpressions instead of two Ints is so that it could handle recursive situations like this:

ArithmeticExpression.Addition(ArithmeticExpression.Addition(ArithmeticExpression.Number(1), ArithmeticExpression.Number(2)), ArithmeticExpression.Number(3))

or, on more than one line:

let addition1 = ArithmeticExpression.Addition(ArithmeticExpression.Number(1), ArithmeticExpression.Number(2))
let addition2 = ArithmeticExpression.Addition(addition1, ArithmeticExpression.Number(3))

which represents:

(1 + 2) + 3

The recursive definition allows you to add not just numbers, but also other arithmetic expressions. That's where the power of this enum lies: it can express multiple nested addition operations.

Coo

Answer 2

PeterPan, I sometimes think that examples that are TOO realistic confuse more than help as it’s easy to get bogged down in trying to understand the example code.

A recursive enum is just an enum with associated values that are cases of the enum's own type. That's it. Just an enum with cases that can be set to associated values of the same type as the enum. #endof

Why is this a problem? And why the key word "indirect" instead of say "recursive"? Why the need for any keyword at all?

Enums are "supposed" to be copied by value which means they should have case associated values that are of predictable size - made up of cases with the basic types like Integer and so on. The compiler can then guess the MAXIMUM possible size of a regular enum by the types of the raw or associated values with which it could be instantiated. After all you get an enum with only one of the cases selected - so whatever is the biggest option of the associated value types in the cases, that's the biggest size that enum type could get on initialisation. The compiler can then set aside that amount of memory on the stack and know that any initialisation or re-assignment of that enum instance could never be bigger than that. If the user sets the enum to a case with a small size associated value it is OK, and also if the user sets it to a case with the biggest associated value type.

However as soon as you define an enum which has a mixture of cases with different sized associated types, including values that are also enums of the same type (and so could themselves be initialised with any of the enums cases) it becomes impossible to guess the maximum size of the enum instance. The user could keep initialising with a case that allows an associated value that is the same type as the enum - itself initialised with a case that is also the same type, and so on and so on: an endless recursion or tree of possibilities. This recursion of enums pointing to enums will continue until an enum is initialised with associated value of "simple" type that does not point to another enum. Think of a simple Integer type that would “terminate” the chain of enums.

So the compiler cannot set aside the correct sized chunk of memory on the stack for this type of enum. Instead it treats the case associated values as POINTERS to the heap memory where the associated value is stored. That enum can itself point to another enum and so on. That is why the keyword is "indirect" - the associated value is referenced indirectly via a pointer and not directly by a value.

It is similar to passing an inout parameter to a function - instead of the compiler copying the value into the function, it passes a pointer to reference the original object in the heap memory.

So that's all there is to it. An enum that cannot easily have its maximum size guessed at because it can be initialised with enums of the same type and unpredictable sizes in chains of unpredictable lengths.

As the various examples illustrate, a typical use for such an enum is where you want to build-up trees of values like a formula with nested calculations within parentheses, or an ancestry tree with nodes and branches all captured in one enum on initialisation. The compiler copes with all this by using pointers to reference the associated value for the enum instead of a fixed chunk of memory on the stack.

So basically - if you can think of a situation in your code where you want to have chains of enums pointing to each other, with various options for associated values - then you will use, and understand, a recursive enum!

Filipino