Types are nice: recursive types, in Swift

Some time ago, I had hopes of completely masking one of my app's services' inner pagination logic. Ideally, that meant my Controllers or ViewModels wouldn't need to know anything about how the service handled pagination. Nothing. Not whether or not there was a next page of results. Not even the parameters needed by the service to retrieve it.

Seems obscure? The gist is quite straightforward:

func getItems() -> (results: [Item], next: (() -> [Item])?)

A recursive function definition

Except our returned next closure should share the return type of getItems, else we'd be limited to the first two pages, wouldn't we?

func getItems() -> (results: [Item], next: (() -> (results: [Item], next: (() -> (results: [Item], next: (() -> ...)?)?)))?)

See what the problem is?

Yeah, our return type is recursive. Our function has a recursive type definition. It basically returns another (optional) version of itself. Which in Swift can be a bit of a pain (meaning it simply isn't an option). So what can we do?

Recursive types

In Swift, recursive types aren't much more fun. Structs can't handle recursive typing. Enums need to be made indirect (see this conversation). Classes can be recursive, but forcing the return type to be a class is another can of worms entirely.

Typealias

Ok, so how about using a typealias ? That should work nicely, right?

typealias PaginatedResult = (value: [Item], next: (() -> PaginatedResult)?)


func getItems() -> PaginatedResult {
	// Function implementation
}

No, won't work. Xcode will call us out for "referencing our typealias inside itself".

Back to enums then.

Enum

enum PaginatedResul {
    indirect case node([Item], (() -> PaginatedResult<Item>)?)

    var value: [Item] {
        if case let PaginatedResult.node(value, _) = self {
            return value
        }
        return []
    }

    var next: (() -> PaginatedResult)? {
        if case let Paginated.node(_, next) = self {
            return next
        }
        return nil
    }
}

Generic enum

enum PaginatedResult<T> {
    indirect case node([T], (() -> PaginatedResult<T>)?)

    var value: [T] {
        if case let PaginatedResult.node(value, _) = self {
            return value
        }
        return []
    }

    var next: (() -> PaginatedResult<T>)? {
        if case let PaginatedResult.node(_, next) = self {
            return next
        }
        return nil
    }
}

Yes, you are right, this can be boiled down to a (potentially asynchronous, if needed) linked list.

Other use cases

Ok, so, apart from weird pagination implementations and linked lists, what are recursive types good for?

Tree structures

Trees are used almost everywhere, although most of us rarely directly use or implement any. Parsing maths to make a calculator in first-year CS? Tree. Parsing code while implementing a code interpreter or compiler? (Abstract Syntax) Tree. Parsing XML or JSON? Tree. Exploring a file system? Tree. Building complex nested UIs? Tree.

Trees all the way!

Graphs

Implementing your own navigation system, like Charly Delaroche? You'll need a graph for that. Tired of Zapier and hell-bent on building a better workflow engine? Graphs (ideally directed and acyclic). Building a state machine to coordinate your onboarding? Graphs.

Epilogue

So that's one way of implementing a recursive type in Swift. If you're interested, some have had some fun and success implementing recursive structs in a similar way using either a generic class or a generic indirect enum, combined with property wrappers.

That's all for me. I hope you found it useful. Please do reach out should you have any questions or suggestions, and have a fantastic day!