Swift struct type recursive value

Question

Structs can't have recursive value types in Swift. So the follow code can't compile in Swift

struct A {
    let child: A
}

A value type can not be recursive, because it would have infinite size.But I wonder why the follow code can compile?

struct A {
    let children: [A]
}

Answer 1

The array doesn't hold its values directly. An array is essentially a struct that holds the reference to an external chunk of memory which contains the items. Therefore all arrays occupy the same amount of memory and there is no problem to use them in structs.

To demonstrate:

struct Value {
    var array: [Int] = [] 
}

var value = Value()
value.array = [0, 1, 2, 3]  // this won't increase the size of the struct!

If arrays behaved differently, you wouldn't be able to change their size dynamically (e.g. append elements) or to use their copy-on-write behavior. In essence, arrays & dictionaries are classes wrapped into value types.

Therefore, your code can compile because it's not really recursive.

Answer 2

I think it's about the required space.

Infinite space

To create a value of this type

struct A {
    let child: A
}

we need

• the space for the current struct
• the space for the child
• the space for the child's child
• ...

So we need infinite space.

Finite space

On the other hand to create a value of this

struct A {
    let children: [A]
}

we only need

• the space for A
• the space for an empty Array.

Answer 3

Since child[] can be empty there is no reason why this shouldn't work. This compiles just fine:

struct Foo {
  let child: [Foo]
}

let foo = Foo(child: [Foo(child:[Foo(child:[]), Foo(child:[])])])

Although I don't see any practical use for it – I wonder if there is, though.

Answer 4

If you know a Node will only ever have one parent (if leaf), then you could use enum and indirect case like so:

public enum Node<Value> {
    case root(value: Value)
    indirect case leaf(parent: Node, value: Value)
}

public extension Node {
    var value: Value {
        switch self {
        case .root(let value): return value
        case .leaf(_, let value): return value
        }
    }
}

If you know that your node will always have two parents, you can just adjust the enum case to accommodate that, etc etc.