Swift struct type recursive value

问题:

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]
}

回答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.

回答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.

回答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.