Is it possible to create a recursive function type in Kotlin?

Question

I have functions that represent steps in a process. Each function also knows the next step, if there is one. I'd like to be able to do something like:

fun fooStep() : Step? {
    ... do something ...
    return ::barStep // the next step is barStep
}

These functions are called from a central dispatching function, which contains code a bit like this:

var step = startStep
while (step != null) {
    step = step()
}

Note that the logic in a particular step also determines the next step, if there even is one.

I thought I could define Step as:

typealias Step = () -> Step?

So a Step is a function that returns another Step, or null. However, this fails to compile with:

Kotlin: Recursive type alias in expansion: Step

I can work around this by wrapping the function in an object. eg:

data class StepWrapper(val step: () -> StepWrapper?)

and changing my function signatures accordingly.

Unfortunately, this means that I cannot just use function literals (eg: ::barStep), but instead have to wrap them in a StepWrapper:

fun fooStep() : StepWrapper? {
    ... do something ...
    return StepWrapper(::barStep)
}

(I also have to change my dispatch loop, accordingly.)

I'd like to avoid the need to create these wrapper objects, if possible. Is there any way to do this in Kotlin?

Kaufman

github.com/Kotlin/KEEP/blob/master/proposals/type-aliases.md Not according to this, at least not using a typealias – Debt

Is there a compelling reason that a Step function needs to know the next step? Another approach would be to have a Step function that returns a Condition, combined with a graph of Step function references. Each node in the graph contains the step function to be called and then a Map<Condition, Step> of what to call next depending on the Condition that is returned. There would then be an executor that could traverse this graph. – Cursory

@roobyroo What is the benefit to the Map<Condition, Step> approach over the StepWrapper approach described in the question? – Kaufman

@Debt Yeah, I didn't expect that it would be possible with typealias, given that it explicitly points out recursive types as being a problem. – Kaufman

@LaurenceGonsalves Here's a simplified example where each function has only one next step: data class Node(val step: () -> Unit, val nextNode: Node?) fun step1(): Unit { println("step 1") } fun step2(): Unit { println("step 2") } val node2 : Node = Node(::step2, null) val node1 : Node = Node(::step1, node2) var curNode: Node? = node1 while (curNode != null) { curNode.step.invoke() curNode = curNode.nextNode } If a function can conditionally return more than one step then the Map is needed. – Cursory

Answer 1

You can define it by using some generic interface:

interface StepW<out T> : ()->T?

interface Step : StepW<Step>


class Step1 : Step {
    override fun invoke(): Step? = Step2()
}

class Step2 : Step {
    override fun invoke(): Step? = null
}

Where Step is your recursive function type.

Scyphate

Interesting! I didn't know that Kotlin would let you extend a function type with an interface. This at least solves the wrapper object problem, though it's too bad that a class is necessary to actually implement this interface. – Kaufman

Answer 2

Here's how you can make it work though I'm really not sure what you're trying to achieve with it:

typealias Fun<T> = () -> T
typealias Step<T> = () -> (T)

typealias Step1 = Step<Fun<Step2>>
typealias Step2 = Step<Fun<Step3>>
typealias Step3 = Step<Unit>

fun step1(): Step1 {
    return {
        println("step 1")
        ::step2
    }
}

fun step2(): Step2 {
    return {
        println("step 2")
        ::step3
    }
}

fun step3(): Step3 {
    return { println("done") }
}

Procrustes

This wouldn't work, as I need all steps to have the same type. Also, a given step does not always have the same following step, or same number of subsequent steps (depending on input), but this approach encodes the entire length of the process in the type. – Kaufman

Answer 3

Use an Enum to implement the state pattern with finite states and prefer returning non-null values. An enum can inherit from a function.

enum class Step : () -> Step {
    Step1 {
        override fun invoke() = Step2
    },
    Step2 {
        override fun invoke() = End
    },
    End {
        override fun invoke() = this
    }
}

fun work() {
    var step = Step.Step1
    while (step !== Step.End) {
        step = step()
    }
}

Claireclairobscure