Building a Sequence Recursively

Support
1

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.

2

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>
)
3 Likes
3

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
4

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