Search code examples
genericskotlinnested-generics

Higher order (or recursive?) generic type parameters in kotlin

I'm prototyping some highly declarative code, and the type inference and safety that comes with Kotlin helps a lot. One of the goals is making extensions (subclasses) of the primary types stupidly easy to implement. In order to maintain rich type inference and expressiveness, I've found some success in defining generic extension functions projected against subclasses. All the type information of subclass methods with none of the extra subclass implementation, it's great.

So I'm trying to write a rich generic function that maintains as much type information as possible. The issue creeps up with the fact that this function operates on potentially recursively generic types, and I want to shuffle the generic type parameters.

This would be impossible to describe without an example. So consider:

open class G<in T>
class A<in T> : G<T>()
class B<in T> : G<T>()
class C<in T> : G<T>()
val ba = B<A<*>>()
val cb = C<B<*>>()

We want a function that effectively can do this, except generically

fun B<A<*>>.doTransitiveThing(c: C<B<*>>) : C<A<*>>
{
    // implement
}

val ca = ba.doTransitiveThing(cb) // Returns C<A<*>>

Goal Criteria:

  • Takes C as a param and returns C, except with different generic type parameter
  • I'd like to generalize this behavior as an extension function of all subclasses of G
    • It needs to be an extension function so that using generic types we can have the type of the subclass and ensure the argument has a generic type argument of the receiver type.
    • Or in other words, we want an extension function for subclasses of G so the argument must be C<B<*>> instead of C<G<*>> when invoked on B<A<*>>

That describes the gist of the problem. I'm not sure the language is capable of supporting what I want. I'm not sure if type erasure is a factor that makes this impossible, but so far I can't find it so (maybe I could use help if it is so).

The following is close

fun <
    TargetGenericType, 
    Arg1Type: G<*>, 
    ReceiverType: G<TargetGenericType>, 
    Arg2Type: G<Arg1Type>, 
    ResultType: G<TargetGenericType>
    >
    ReceiverType.doTransitiveThingGeneric(x: Arg2Type): ResultType
{
    //implement
}
val ca2 = ba.doTransitiveThingGeneric(cb)

but there are a few problems

  • It returns G<A<*>> instead of C<A<*>>. It would be nice if it could return C and not lose type information (otherwise I don't really have a use for this function anyway)
  • There is technically no guarantee ReceiverType is Arg1Type

Thinking ahead, if something like the following was valid Kotlin, I think it would address my problem

fun <
    TargetGenericType,
    ReceiverBaseType<T>: G<T>,
    typealias ReceiverType = ReceiverBaseType<TargetGenericType>,
    ParamBaseType<U>: G<U>,
    typealias ParamType = ParamBaseType<ReceiverBaseType<*>>,
    ResultType: ParamBaseType<TargetGenericType>
    >
    ReceiverType.doTransitiveThingHigherOrderGeneric(x: ParamType): ResultType
{
    //implement
}

Is there a reason it can't be done? e.g. added as a feature on the language? I am sympathetic to logistical reasons against, but I'm curious if it is even possible in principle too.

Last notes:

  • It reminds me of type aliases except for generic type parameters themselves. In fact I've included that keyword in the example in case it helps to digest. That isn't the only part though, notice <T> and <U> in the syntax.
  • It almost reminds me of Monads as well, except with class definitions themselves if that makes sense in a sort of hand wavy, intuitive way.
  • I have no idea how to implement the body yet, but I haven't gotten that far since I'm still trying to see if the signature is even possible :p
Solution

  • Ultimately what I was looking for is higher kinds. I was trying to force it all into one single overly nested type constructor. The manipulations I wanted to accomplish cannot be achieved that way, and must be done using multiple type parameters. The functional library Arrow's description of higher kinds helped me realize that.

    In a Higher Kind with the shape Kind<F, A>, if A is the type of the content then F has to be the type of the container.

    A malformed Higher Kind would use the whole type constructor to define the container, duplicating the type of the content Kind<Option<A>, A>. This incorrect representation has large a number of issues when working with partially applied types and nested types.