[Pitch] Add recursiveMap(_:) methods

Hello everyone,

I want to introduce a SQL's recursive CTE like operation to Swift.

recursiveMap

Introduction

Bring SQL's recursive CTE like operation to Swift. This method traverses all nodes of the tree and produces a flat sequence.

Swift forums thread: Discussion thread topic for that proposal

Proposed Solution

Produces a sequence containing the original sequence and the recursive mapped sequence. The order of ouput elements affects by the traversal option.

struct Node {
    var id: Int
    var children: [Node] = []
}
let tree = [
    Node(id: 1, children: [
        Node(id: 2),
        Node(id: 3, children: [
            Node(id: 4),
        ]),
        Node(id: 5),
    ]),
    Node(id: 6),
]
for await node in tree.async.recursiveMap({ $0.children.async }) {
    print(node.id)
}
// 1
// 2
// 3
// 4
// 5
// 6

Traversal Option

This function comes with two different traversal methods. This option affects the element order of the output sequence.

  • depthFirst: The algorithm will go down first and produce the resulting path. The algorithm starts with original
    sequence and calling the supplied closure first. This is default option.

    With the structure of tree:

    let tree = [
        Node(id: 1, children: [
            Node(id: 2),
            Node(id: 3, children: [
                Node(id: 4),
            ]),
            Node(id: 5),
        ]),
        Node(id: 6),
    ]
    

    The resulting sequence will be 1 -> 2 -> 3 -> 4 -> 5 -> 6

    The sequence using a buffer keep tracking the path of nodes. It should not using this option for searching the indefinite deep of tree.

  • breadthFirst: The algorithm will go through the previous sequence first and chaining all the occurring sequences.

    With the structure of tree:

    let tree = [
        Node(id: 1, children: [
            Node(id: 2),
            Node(id: 3, children: [
                Node(id: 4),
            ]),
            Node(id: 5),
        ]),
        Node(id: 6),
    ]
    

    The resulting sequence will be 1 -> 6 -> 2 -> 3 -> 5 -> 4

    The sequence using a buffer storing occuring nodes of sequences. It should not using this option for searching the indefinite length of occuring sequences.

Detailed Design

The recursiveMap(option:_:) method is declared as AsyncSequence extensions, and return AsyncRecursiveMapSequence or AsyncThrowingRecursiveMapSequence instance:

extension AsyncSequence {
    public func recursiveMap<S>(
        option: AsyncRecursiveMapSequence<Self, S>.TraversalOption = .depthFirst,
        _ transform: @Sendable @escaping (Element) async -> S
    ) -> AsyncRecursiveMapSequence<Self, S>
    
    public func recursiveMap<S>(
        option: AsyncThrowingRecursiveMapSequence<Self, S>.TraversalOption = .depthFirst,
        _ transform: @Sendable @escaping (Element) async throws -> S
    ) -> AsyncThrowingRecursiveMapSequence<Self, S>
}

For the non-throwing recursive map sequence, AsyncRecursiveMapSequence will throw only if the base sequence or the transformed sequence throws. As the opposite side, AsyncThrowingRecursiveMapSequence throws when the base sequence, the transformed sequence or the supplied closure throws.

The sendability behavior of Async[Throwing]RecursiveMapSequence is such that when the base, base iterator, and element are Sendable then Async[Throwing]RecursiveMapSequence is Sendable.

Complexity

Calling this method is O(1).

Effect on API resilience

none.

Alternatives considered

none.

Acknowledgments

none.

2 Likes

Several questions:

  • Why is this restricted to async? Do we have non-async counterpart of this function?
  • Given that it is does not map the tree recursively, but instead flattens it, should we name it by something like flatten(recursivelyInto:)?
  • If we don’t need to preserve the order, we can have the mapping closure dispatched in parallel with taskGroup, which can maximum the efficiency. I wonder if it’s possible to make this.
My first impression of `recursiveMap`
let tree = [
    Node(id: 1, children: [
        Node(id: 2),
        Node(id: 3, children: [
            Node(id: 4),
        ]),
        Node(id: 5),
    ]),
    Node(id: 6),
]
tree.recursiveMap(through: \.children) { node, mappedChildren in
    AnotherNode(id: node.id + 1, children: mappedChildren)
}

Yes, I have create a pull request for the non-async version:

I have no idea what's the name of this operation. So I just named it arbitrarily.

However, flatten(recursivelyInto:) may not a good name because it cause ambiguity with flatMap(_:) when we write code with trailing closure.

I think that would be a eager breadth first traversal, which would run out of memory with large/infinity length of sequence easily.