I have a tree-like recursive structure that I'd li...

# getting-started

[CLOVIS]

I have a tree-like recursive structure that I'd like to deep-copy and replace elements.

Ideally, something like

foo.visit {
    if (it is Foo && it.name == "foo")
        it.copy(name = "bar")
    else
        it
}

However, it must be forbidden to return another type that the exact input type. That is, if it is Foo , then the lambda must return an instance of Foo . If it is Bar , then the lambda must return an instance of Bar . This makes this hard to represent with type parameters as they expected to be user-supplied, where here they should be data-supplied.

Is there a way to represent this?

[joseph_ivie]

Not totally sure if I'm following, but I think I may have tackled a similar problem before and came up with a reasonable approach. Can you put the actual data structure in here, or something like it?

[joseph_ivie]

You can certainly do better than this, but this was the general idea:

import kotlin.reflect.KClass

interface DeepTypedCopyable<T> {
    interface TypeVisitor {
        fun handle(any: Any): Any
        companion object
    }
    fun copy(visitor: TypeVisitor): T
}

class TypeVisitorBuilder {
    val handlers = ArrayList<Pair<KClass<*>, (Any)->Any>>()
    inline fun <reified T> handle(noinline action: (T) -> T) {
        handlers.add(T::class to action as (Any)->Any)
    }
    fun build(): DeepTypedCopyable.TypeVisitor = object: DeepTypedCopyable.TypeVisitor {
        override fun handle(any: Any): Any {
            val handler = handlers.find { it.first.isInstance(any) } ?: return any
            return handler.second(any)
        }
    }
}
inline fun DeepTypedCopyable.TypeVisitor.Companion.create(builder: TypeVisitorBuilder.()->Unit) = TypeVisitorBuilder().apply(builder).build()
inline fun <T> DeepTypedCopyable<T>.copy(crossinline builder: TypeVisitorBuilder.()->Unit): T = copy(DeepTypedCopyable.TypeVisitor.create(builder))

data class Sample(
    val left: Sample? = null,
    val right: Sample2? = null,
    val number: Int = 10,
): DeepTypedCopyable<Sample> {
    override fun copy(visitor: DeepTypedCopyable.TypeVisitor): Sample = copy(
        left = left?.copy(visitor),
        right = right?.copy(visitor),
    )
}

data class Sample2(
    val top: Sample? = null,
    val bottom: Sample2? = null,
    val string: String = "asdf",
): DeepTypedCopyable<Sample2> {
    override fun copy(visitor: DeepTypedCopyable.TypeVisitor): Sample2 = copy(
        top = top?.copy(visitor),
        bottom = bottom?.copy(visitor),
    )
}

fun example(sample: Sample) {
    sample.copy {
        handle<Sample> { it.copy(number = 10) }
        handle<Sample2> { it.copy(string = "fdsa") }
    }
}

[Youssef Shoaib [MOD]]

One puzzle piece here that may help is rank-2 polymorphism. https://kotlinlang.slack.com/archives/C5UPMM0A0/p1748204869774789
Also the upcoming GADT smartcasting may help too

[CLOVIS]

Can you put the actual data structure in here, or something like it?

I can't share the exact one, but it's a fairly standard recursive type.

interface Foo {
    val parents: List<Foo>
}

class Unary(val a: Foo): Foo {
    override val parents get() = listOf(a)
}

class Binary(val a: Foo, val b: Unary): Foo {
    override val parents get() = listOf(a, b)
}

However, they don't all accept all values. For example, Binary 's second argument must be a Unary , so when mapping/visiting that subtree, the type must remain the same.

[joseph_ivie]

Sounds like the solution I posted might still work then!

[CLOVIS]

@joseph_ivie Interesting solution! However, in your example, Sample and Sample2 don't have a common interface (other than DeepTypedCopyable).

If possible, I'd prefer:

DeepTypedCopyable
            |
       FooInterface
        /       \
    Sample     Sample2

but I can't write

interface FooInterface : DeepTypedCopyable<FooInterface>

because that would lock the type parameter for all children

[joseph_ivie]

Hmmm.... good point.

[CLOVIS]

I've adapted your example to

interface SelfVisiting<Self : SelfVisiting<Self>> {

    fun visit(
        visitor: (Any) -> Any,
    ): Self
}

fun <Self : SelfVisiting<Self>> Self.transform(
    block: SelfVisitingDsl<Self>.() -> Unit,
): SelfVisiting<Self> {
    // Register all mappings
    val mappings = ArrayList<Pair<KClass<*>, (Any) -> Any>>()
    val dsl = object : SelfVisitingDsl<Self> {
        override fun <T : Self> map(kClass: KClass<T>, mapping: (T) -> T) {
            @Suppress("UNCHECKED_CAST")
            mappings.add(kClass to (mapping as (Any) -> Any))
        }
    }
    block(dsl)

    return visit { node ->
        val mapper = mappings.find { it.first.isInstance(node) }

        if (mapper != null)
            mapper.second(node)
        else
            node
    }
}

interface SelfVisitingDsl<S : SelfVisiting<S>> {
    fun <T : S> map(kClass: KClass<T>, mapping: (T) -> T)
}

inline fun <S : SelfVisiting<S>, reified T : S> SelfVisitingDsl<S>.map(noinline action: (T) -> T) {
    map(T::class, action)
}

I'm not saying it's better (technically it's the same) but I find it easier to read

[joseph_ivie]

That works! Yeah, the snippet I gave wasn't out of a library, it was just a scratch file that demonstrated the concept. I think it could be improved further via inlining tricks in the DSL to avoid keeping the ArrayList, too. Keeping KClasses around isn't something I love either

[joseph_ivie]

Hold on, I have an idea now.

[CLOVIS]

I think I got it:

interface Visiting<Top : Visiting<Top>> {

    fun visit(
        visitor: (Top) -> Top,
    ): Visiting<Top>
}

interface SelfVisiting<Top : Visiting<Top>, Self : SelfVisiting<Top, Self>> : Visiting<Top> {

    override fun visit(
        visitor: (Top) -> Top,
    ): Self
}

fun <Top : Visiting<Top>> Top.transform(
    block: SelfVisitingDsl<Top>.() -> Unit,
): Visiting<Top> {
    // Register all mappings
    val mappings = ArrayList<Pair<KClass<*>, (Top) -> Top>>()
    val dsl = object : SelfVisitingDsl<Top> {
        override fun <U : Top> map(kClass: KClass<U>, mapping: (U) -> U) {
            @Suppress("UNCHECKED_CAST")
            mappings.add(kClass to (mapping as (Top) -> Top))
        }
    }
    block(dsl)

    return visit { node ->
        val mapper = mappings.find { it.first.isInstance(node) }

        if (mapper != null)
            mapper.second(node)
        else
            node
    }
}

interface SelfVisitingDsl<T: Visiting<T>> {
    fun <U : T> map(kClass: KClass<U>, mapping: (U) -> U)
}

inline fun <T: Visiting<T>, reified U : T> SelfVisitingDsl<T>.map(noinline action: (U) -> U) {
    map(U::class, action)
}


interface FooInterface : Visiting<FooInterface>

data class Sample(
    val left: Sample? = null,
    val right: Sample2? = null,
    val number: Int = 10,
): FooInterface, SelfVisiting<FooInterface, Sample> {

    override fun visit(visitor: (FooInterface) -> FooInterface): Sample = copy(
        left = left?.visit(visitor),
        right = right?.visit(visitor)
    )
}

data class Sample2(
    val top: Sample? = null,
    val bottom: Sample2? = null,
    val string: String = "asdf",
): FooInterface, SelfVisiting<FooInterface, Sample2> {

    override fun visit(visitor: (FooInterface) -> FooInterface): Sample2 = copy(
        top = top?.visit(visitor),
        bottom = bottom?.visit(visitor),
    )
}

fun example(sample: Sample) {
    sample.transform {
        map { it: Sample -> it.copy(number = 10) }
        map { it: Sample2 -> it.copy(string = "fdsa") }
    }
}

[CLOVIS]

Thanks for the help! I didn't expect at all that this would work

[CLOVIS]

Honestly I'm still not sure why

return visit { node ->
        val mapper = mappings.find { it.first.isInstance(node) }

        if (mapper != null)
            mapper.second(node)
        else
            node
    }

typechecks

[CLOVIS]

especially in your version

[joseph_ivie]

In mine, it's "typechecked" to Any, so I suppose as long as it isn't null it can't fail

[CLOVIS]

fun example(sample: Sample): Sample {
    return sample.copy {
        handle<Sample> { it.copy(number = 12) }
        handle<Sample2> { it.copy(string = "other") }
    }
}

val input = Sample(null, Sample2(Sample(Sample()), string = "text"))
val output = example(input)

println(output)

It still returns string=text , the handlers are not executed 😅

[CLOVIS]

During the recursion on DeepTypedCopyable.copy , visitor is never called

[CLOVIS]

The sample classes should probably be something like

data class Sample(
    val left: Sample? = null,
    val right: Sample2? = null,
    val number: Int = 10,
): DeepTypedCopyable<Sample> {
    override fun copy(visitor: DeepTypedCopyable.TypeVisitor): Sample = copy(
        left = left?.copy(visitor),
        right = right?.copy(visitor),
    ).let(visitor::handle) // ⚠!
}

but that cannot typecheck as the visitor returns Any

[Youssef Shoaib [MOD]]

This works as expected:

interface Foo<T : Foo<T>> {
  fun accept(visitor: FooVisitor): T
}

interface FooVisitor {
  fun <T: Foo<T>> visit(foo: T): T
}

data class Leaf(val text: String) : Foo<Leaf> {
  override fun accept(visitor: FooVisitor) = visitor.visit(this)
}

// mimicking subtype reconstruction
@Suppress("UNCHECKED_CAST", "FINAL_UPPER_BOUND")
fun <L: Leaf> L.myCopy(text: String = this.text): L = copy(text = text) as L

data class Unary<T : Foo<T>>(val a: T) : Foo<Unary<T>> {
  override fun accept(visitor: FooVisitor): Unary<T> = visitor.visit(copy(a = a.accept(visitor)))
}

data class Binary<T: Foo<T>, U: Foo<U>>(val a: T, val b: Unary<U>) : Foo<Binary<T, U>> {
  override fun accept(visitor: FooVisitor): Binary<T, U> =
    visitor.visit(copy(a = a.accept(visitor), b = b.accept(visitor)))
}

fun main() {
  val hello = Unary(Unary(Unary(Unary(Leaf("hello")))))
  val complex = Binary(
    Unary(Unary(Leaf("hello"))),
    Unary(Unary(Leaf("no")))
  )
  val helloToWorldTransform = object : FooVisitor {
    override fun <T : Foo<T>> visit(foo: T): T = when (foo) {
      is Leaf if foo.text == "hello" -> foo.myCopy(text = "world")
      else -> foo
    }
  }
  hello.accept(helloToWorldTransform).also(::println)
  complex.accept(helloToWorldTransform).also(::println)
}

The trick is in the myCopy function which is never "unsafe" since you can prove that T: Leaf implies T == Leaf. The need for such a function goes away with subtype reconstruction.
This sadly can't use lambdas easily. There is a trick I mentioned above using Raise, but it's very weak since Kotlin has very very rudimentary support for existential types.

[CLOVIS]

>

// mimicking subtype reconstruction
> @Suppress("UNCHECKED_CAST", "FINAL_UPPER_BOUND")

Does this mean this @Suppress can be removed once the subtype reconstruction KEEP lands? Or even that myCopy can be entirely replaced by the regular .copy ?

[Youssef Shoaib [MOD]]

Both!

[CLOVIS]

Nice!

[CLOVIS]

Thanks a lot for that, that's very promising

[Youssef Shoaib [MOD]]

Lmk how it goes!