Building a Sequence Recursively

Disclaimer: my understanding of coroutines is weak.

I have a tree which from which I wish to create a sequence.
Some of the branches of the tree will be pruned away using a function.

fun drillDown(
    sequenceScope: SequenceScope<TreeNode>,
    base: TreeNode,
    pruner: (node: TreeNode) -> Boolean
) {
    base.children.forEach { child ->
        if (pruner(child)) {
            sequenceScope.yield(child)
            drillDown(sequenceScope, child, pruner)
        }
    }
}

This is called via…

val seq0 = sequence { 
       drillDown(this, root, pruner)
}

In Intellij/IDEA I get the message…
‘Suspend function ‘yield’ should be called only from a coroutine or another suspend function’.

The recommendation I get from IDEA is “Make ‘drillDown’ suspend”.
I blindly tried that but I caused other errors.

The issue comes down to being able to call the ‘yield’ function from within a recursive function.
Any advice?

TreeNode.kt

data class TreeNode(
    val children: List<TreeNode>
    )

The actual implementation has more parts but this example should be enough to motivate the question.

You need to make the function suspend and an extension on SequenceScope, because SequenceScope is defined as @RestrictsSuspension, which means that it uses suspend in a special way, and hence it isn’t a special suspend function. IMO the code even looks cleaner this way:

suspend fun SequenceScope<TreeNode>.drillDown(
    base: TreeNode,
    pruner: (node: TreeNode) -> Boolean
) {
    base.children.forEach { child ->
        if (pruner(child)) {
            yield(child)
            drillDown(child, pruner)
        }
    }
}
data class TreeNode(
    val children: List<TreeNode>
)
2 Likes

Excellent!
Here are the docs for what was referenced.

The calling function needs a little tweak as well.

val seq0 = sequence { 
       drillDown(root, pruner)
}

I am not sure what you mean by “a special suspend function”.
It seems like if it uses ‘suspend’ in a special way it should be a special suspend function.
In any case, thanks.

1 Like

functions that have a receiver annotated with @RestrictsSuspension are not allowed to call arbitrary suspend methods, hence they’re “special” in that it forces you to call only other functions that take the same type as a receiver, such as yield. What that ultimately means is that sequence does some special behind-the-scenes work with the coroutines machinery. In this case, sequences don’t produce new values until a value is required, so the function passed to the sequence is suspended until required.

3 Likes