Unorthodox recursive data structures

Using Swift
, ,
1

The topic name is a bit misleading as what's discussed here:

  • could be mutable
  • could be truly allocation free, could be stack allocated or in some cases uses heap allocation behind the curtains.
  • could be truly dynamic (including cases that do not involve heap allocation)
  • could contain cycles (so not just a list or a tree).

Posting this here so we don't sidetrack the other thread.

Just like other structures that split into mutable and immutable versions (like NSString vs NSMutableString), you can actually implement immutable (†) recursive data structures in Swift. Interestingly, Swift can do this without classes, indirect enums, or storing node children in an array. There are at least three different ways to handle this, allowing for immutable recursive data structures of arbitrary lengths (though still subject to compiler limits). In at least one of those setups, there's no side allocation at all – the structure is purely inline (see case C).

A. Protocol with an Optional for termination

protocol ANode {
    var next: ANode? { get }
}
struct A: ANode {
    let name: String
    let next: ANode?
    init(_ name: String, _ next: ANode? = nil) { self.name = name; self.next = next }
}
let a = A("veni ", A("vidi ", A("vici ", A("."))))
print(a)
// A(name: "veni ", next: Optional(A(name: "vidi ", next: Optional(A(name: "vici ", next: Optional(A(name: ".", next: nil)))))))

B. Protocol with a second note type for termination

protocol BNode {
    var hasNext: Bool { get }
    var next: BNode { get }
}
struct B: BNode {
    let name: String
    var hasNext: Bool { true }
    let next: BNode
    init(_ name: String, _ next: BNode) { self.name = name; self.next = next }
}
struct BL: BNode {
    var hasNext: Bool { false }
    var next: BNode { fatalError() }
}
let b = B("veni ", B("vidi ", B("vici ", B(".", BL()))))
print(b)
// B(name: "veni ", next: B(name: "vidi ", next: B(name: "vici ", next: B(name: ".", next: BL()))))

C. Generics with a second node type for termination

struct C<Next> {
    var name: String
    var next: Next
    init(_ name: String, _ next: Next) { self.name = name; self.next = next }
}
struct CL {}
let c = C("veni ", C("vidi ", C("vici ", C(".", CL()))))
print(c)
struct CL: CNode {}
// C<C<C<C<CL>>>>(name: "veni ", next: C<C<C<CL>>>(name: "vidi ", next: C<C<CL>>(name: "vici ", next: C<CL>(name: ".", next: CL()))))

What's the actual size of these data structures?

With C it is as expected, growing with the number of fields:

print(MemoryLayout.size(ofValue: CL())) // 0
print(MemoryLayout.size(ofValue: C(".", CL()))) // 16
print(MemoryLayout.size(ofValue: C("vici ", C(".", CL())))) // 32
print(MemoryLayout.size(ofValue: C("vidi ", C("vici ", C(".", CL()))))) // 48
print(MemoryLayout.size(ofValue: C("veni ", C("vidi ", C("vici ", C(".", CL())))))) // 64

indicating that all storage is inline.

However with A & B the actual contents is stored indirectly:

print(MemoryLayout.size(ofValue: A("."))) // 56
print(MemoryLayout.size(ofValue: A("vici ", A(".")))) // 56
print(MemoryLayout.size(ofValue: A("vidi ", A("vici ", A("."))))) // 56
print(MemoryLayout.size(ofValue: A("veni ", A("vidi ", A("vici ", A(".")))))) // 56

print(MemoryLayout.size(ofValue: BL())) // 0
print(MemoryLayout.size(ofValue: B(".", BL()))) // 56
print(MemoryLayout.size(ofValue: B("vici ", B(".", BL())))) // 56
print(MemoryLayout.size(ofValue: B("vidi ", B("vici ", B(".", BL()))))) // 56
print(MemoryLayout.size(ofValue: B("veni ", B("vidi ", B("vici ", B(".", BL())))))) // 56

which means A & B do allocate memory on the side.

Hope these data structures could be useful in some of real world projects. Plus, you've now got a few more interview questions (and answers) up your sleeve :slight_smile:

† in fact it's possible to mutate some of the fields to some extent, with a simple modification things like this are possible:

a.next?.next?.name = "HOHOHO"
a.next?.next?.next = nil

The most rigid case is C which would allow mutation of all fields apart from next.

2 Likes
Indirect enums vs classes
Indirect Members
2

Does this one count?

struct DNode {
  var name: String
  private var _next: (() -> DNode)? = nil
  var next: DNode? {
    get { _next?() }
    set { _next = newValue.map { next in { next } } }
  }
  init(name: String, next: DNode?) {
    self.name = name
    self.next = next // calls setter
  }
}

(and its slight variant where the optional is inside the closure)

Like the protocol ones, this is ultimately built on another language feature that can use heap allocation: closures.

2 Likes
3

Nice.

And this is truly dynamic and heap-allocation-free one:

S. Stack allocated instead of heap

struct SNode {
    var name: String
    var next: UnsafePointer<SNode>?
}

func buildList(tail: UnsafePointer<SNode>? = nil, depth: Int, execute: (UnsafePointer<SNode>?) -> Void) {
    if depth == 0 {
        execute(tail)
    } else {
        var node = SNode(name: String(depth), next: tail)
        buildList(tail: &node, depth: depth - 1, execute: execute)
    }
}

func printList(_ node: UnsafePointer<SNode>?) {
    if let node = node?.pointee {
        print(node.name, terminator: " ")
        printList(node.next)
    } else {
        print("")
    }
}

buildList(depth: 10) { list in
    printList(list) // 1 2 3 4 5 6 7 8 9 10 
}
Could have cycles 😀 
struct SNode {
    var name: String
    var next: UnsafeMutablePointer<SNode>?
}

var firstNode: UnsafeMutablePointer<SNode>? 

func buildList(tail: UnsafeMutablePointer<SNode>? = nil, depth: Int, execute: (UnsafeMutablePointer<SNode>?) -> Void) {
    if firstNode == nil { firstNode = tail }
    if depth == 0 {
        // pointing the first node to the last
        firstNode?.pointee.next = tail
        execute(tail)
    } else {
        var node = SNode(name: String(depth), next: tail)
        buildList(tail: &node, depth: depth - 1, execute: execute)
    }
}

func printList(_ node: UnsafeMutablePointer<SNode>?, depth: Int = 0, maxDepth: Int) {
    if depth > maxDepth {
        print("...")
        return
    }
    if let node = node?.pointee {
        print(node.name)
        printList(node.next, depth: depth + 1, maxDepth: maxDepth)
    } else {
        print("")
    }
}

buildList(depth: 10) { list in
    printList(list, maxDepth: 30)
}