Recursive structs

Loooop · November 7, 2019, 11:24am

Swift does not allow recursive structs, but there is a very simple trick to get them anyway.

Note: I know that you can directly use only an enum to get the same result. I just want to point out that in this way it is possible to obtain recursive structs.

A simple immutable linked list struct based:

// the trick
enum Recurse<T> {
	indirect case next(T)
	
	var data : T {
		switch self {
		case .next( let data ): return data
		}
	}
}

// a basic immutable single linked list struct based
struct LinkedList<Element> {
	let 		head:	Element?
	private let next:	Recurse<LinkedList<Element>>?

	var tail : LinkedList<Element>? {
		return next?.data ?? nil
	}

	init() {
		self.head	= nil
		self.next	= nil
	}
	
	init( head:Element, tail: LinkedList<Element>? = nil ) {
		self.head	= head
		self.next	= tail.flatMap { Recurse.next( $0 ) }
	}
}

// a characterList example:

extension LinkedList where Element == Character {
	init<T:StringProtocol>( string:T ) {
		if let character = string.first {
			self.init( head:character, tail:LinkedList( string: string.dropFirst() ) )
		} else {
			self.init()
		}
	}
}

extension LinkedList : CustomStringConvertible where Element == Character  {
	var description: String {
		return head.flatMap { String( $0 ) + (tail?.description ?? "") } ?? ""
	}
}

let characterList = LinkedList( string: "Hello World!" )
print( characterList )

P.S. I'm sorry for my bad English.

cukr · November 7, 2019, 11:45am

Simpler version using property wrapper, and autogenerated inits

@propertyWrapper
class Indirect<T> {
    var wrappedValue: T
    init(wrappedValue: T) {
        self.wrappedValue = wrappedValue
    }
}

struct LinkedList<Element> {
    let head: Element?
    @Indirect var tail: LinkedList<Element>?
}

sveinhal · November 7, 2019, 1:07pm

Combining your ideas:

@propertyWrapper
enum Indirect<T> {
    indirect case next(T)
    init(wrappedValue: T) {
        self = .next(wrappedValue)
    }
    var wrappedValue: T {
        switch self {
        case .next(let value): return value
        }
    }
}

struct LinkedList<T> {
    let head: T
    @Indirect var tail: LinkedList<T>?
}

If you only want to use value types.

Loooop · November 7, 2019, 2:35pm

Hi, sveinhal,
it doesn't seem to work.
What am I doing wrong?

anandabits · November 7, 2019, 3:06pm

You need a setter for wrappedValue, like this:


@propertyWrapper
enum Indirect<T> {
    indirect case storage(T)
    init(wrappedValue: T) {
        self = .storage(wrappedValue)
    }
    var wrappedValue: T {
        get {
            switch self {
            case .storage(let value): return value
            }
        set {
            self = .storage(newValue)
        }
    }
}

sveinhal · November 7, 2019, 4:06pm

The struct will get a synthesized initializer that does the rihght thing. If you want to write your own initializer, you must either initialize the underlying _tail property like so:

@propertyWrapper
enum Indirect<T> {
    indirect case next(T)
    init(wrappedValue: T) {
        self = .next(wrappedValue)
    }
    var wrappedValue: T {
        switch self {
        case .next(let value): return value
        }
    }
}

struct LinkedList<Element> {
    let head: Element?
    @Indirect var tail: LinkedList<Element>?

    init() {
        self.head = nil
        self._tail = .next(nil)
    }

    init(head: Element, tail: LinkedList<Element>? = nil) {
        self.head = head
        self._tail = .next(tail)
    }
}

… or make the @Indirect wrapper mutable by creating a setter, like suggested above. However, I made it immutable to mimic the let for the head.

michelf · November 7, 2019, 5:50pm

It's a bit unfortunate that the indirect optional will make a useless heap allocation when storing a nil value. This is probably slightly less wasteful:

@propertyWrapper
enum IndirectOptional<T> {
    case none
    indirect case some(T)
    init(wrappedValue: T?) {
		if let wrappedValue = wrappedValue {
			self = .some(wrappedValue)
		} else {
			self = .none
		}
    }
    var wrappedValue: T? {
		get {
			switch self {
			case .none: return nil
			case .some(let value): return value
			}
		}
		set {
			if let newValue = newValue {
				self = .some(newValue)
			} else {
				self = .none
			}
		}
    }
}

struct LinkedList<T> {
    let head: T
    @IndirectOptional var tail: LinkedList<T>?
}

Loooop · November 8, 2019, 5:20am

It is even more unfortunate that, regardless of how the recursion is programmed, even not too large lists always crash during deallocation.

import Foundation

@propertyWrapper
enum Indirect<T> {
    indirect case storage(T)
    init(wrappedValue: T) {
        self = .storage(wrappedValue)
    }
    var wrappedValue: T {
        get {
            switch self {
            case .storage(let value):
				return value
            }
		}
        set {
            self = .storage( newValue )
        }
    }
}

struct LinkedList<Element> {
    let head: Element?
    @Indirect var tail: LinkedList<Element>?
	
	init() {
		self.head	= nil
		self.tail	= nil
	}
	
	init( head:Element, tail: LinkedList<Element>? = nil ) {
		self.head	= head
		self.tail	= tail
	}
}

extension LinkedList where Element == Int {
	init( count:Int ) {
		// I don't use recursion here
		if count > 0 {
			var tail = LinkedList( head:count-1 )
			for i in 1..<count {
				tail = LinkedList(head: count-i-1, tail: tail)
			}
			self = tail
		} else {
			self.init()
		}
	}
}

extension LinkedList:CustomStringConvertible where Element == Int {
	var description: String {
		return head.flatMap { String($0) + "," + (tail?.description ?? "END") } ?? "END"
	}
}

print("*** shortList")
do {
	let shortList = LinkedList(count: 10)
	print( shortList )
}

print("*** longList")
do {
	let count			= 60000 // will crash; 50000 is ok on my iMac
	
	let start			= DispatchTime.now()
	let longList		= LinkedList(count: count)
	let end 			= DispatchTime.now()
	let nanoTime		= end.uptimeNanoseconds - start.uptimeNanoseconds
	print( longList.head! )
	print( longList.tail!.head! )
	print( longList.tail!.tail!.head! )
	print( longList.tail!.tail!.tail!.head! )
	print( "..." )

	let timeInterval	= Double(nanoTime) / 1_000_000_000
	print("Time: \(timeInterval) seconds")
} // Crash freeing longList for not too large count

print("End")

andrekandore · May 28, 2023, 3:41am

sorry to bring up an old thread, but i also came across this issue and tried this example encountering the same crash even in swift 5.8

i was able to determine that it looks like the stack was busted (call stack too deep) and it seems setting the stack size to 16MB* allows larger recursion up to at least 8000 (compared to 6000 in the example)

other linker settings = -Wl,-stack_size,1000000

this looks like a compiler bug, or perhaps its by design.. in which case i wonder if there is a specific swift-centric annotation that can turn that dealloc into a loop instead of expanding like that...