Generic transpose (or anything else really!) in Kotlin

user_7729724 0
Viewed 170

Working on an Advent of Code puzzle I had found myself defining a function to transpose matrices of integers:

fun transpose(xs: Array<Array<Int>>): Array<Array<Int>> {
    val cols = xs[0].size // 3
    val rows = xs.size // 2
    var ys = Array(cols) { Array(rows) { 0 } }
    for (i in 0..rows - 1) {
        for (j in 0..cols - 1)
            ys[j][i] = xs[i][j]
    }
    return ys
}

Turns out that in the following puzzle I also needed to transpose a matrix, but it wasn't a matrix of Ints, so i tried to generalize. In Haskell I would have had something of type

transpose :: [[a]] -> [[a]]

and to replicate that in Kotlin I tried the following:

fun transpose(xs: Array<Array<Any>>): Array<Array<Any>> {
    val cols = xs[0].size
    val rows = xs.size
    var ys = Array(cols) { Array(rows) { Any() } } // maybe this is the problem?
    for (i in 0..rows - 1) {
        for (j in 0..cols - 1)
            ys[j][i] = xs[i][j]
    }
    return ys
}

This seems ok but it isn't. In fact, when I try calling it on the original matrix of integers I get Type mismatch: inferred type is Array<Array<Int>> but Array<Array<Any>> was expected. The thing is, I don't really understand this error message: I thought Any was a supertype of anything else?

Googling around I thought I understood that I should use some sort of type constraint syntax (sorry, not sure it's called like that in Kotlin), thus changing the type to fun <T: Any> transpose(xs: Array<Array<T>>): Array<Array<T>>, but then at the return line I get Type mismatch: inferred type is Array<Array<Any>> but Array<Array<T>> was expected

So my question is, how do I write a transpose matrix that works on any 2-dimensional array?

kotlin polymorphism generics
1 Answers

As you pointed out yourself, the line Array(cols) { Array(rows) { Any() } } creates an Array<Array<Any>>, so if you use it in your generic function, you won't be able to return it when Array<Array<T>> is expected.

Instead, you should make use of this lambda to directly provide the correct value for the correct index (instead of initializing to arbitrary values and replacing all of them):

inline fun <reified T> transpose(xs: Array<Array<T>>): Array<Array<T>> {
    val cols = xs[0].size
    val rows = xs.size
    return Array(cols) { j ->
        Array(rows) { i -> 
            xs[i][j]
        }
    }
}

I don't really understand this error message: I thought Any was a supertype of anything else?

This is because arrays in Kotlin are invariant in their element type. If you don't know about generic variance, it's about describing how the hierarchy of a generic type compares to the hierarchy of their type arguments.

For example, assume you have a type Foo<T>. Now, the fact that Int is a subtype of Any doesn't necessarily imply that Foo<Int> is a subtype of Foo<Any>. You can look up the jargon, but essentially you have 3 possibilities here:

  • We say that Foo is covariant in its type argument T if Foo<Int> is a subtype of Foo<Any> (Foo types "vary the same way" as T)
  • We say that Foo is contravariant in its type argument T if Foo<Int> is a supertype of Foo<Any> (Foo types "vary the opposite way" compared to T)
  • We say that Foo is invariant in its type argument T if none of the above can be said

Arrays in Kotlin are invariant. Kotlin's read-only List, however, is covariant in the type of its elements. This is why it's ok to assign a List<Int> to a variable of type List<Any> in Kotlin.

user_15408180
Related