Generic transpose (or anything else really!) in Kotlin-CodePudding

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?

CodePudding user response：

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]
        }
    }
}

CodePudding user response：

In Java - and in turn Kotlin - generic types like in Arrays are erased during runtime. One way to solve this with Kotlin is to use a reified type argument.

inline fun <reified T> transpose(xs: Array<Array<T>>): Array<Array<T>>

To create an Array of a specific length, you need an init function for the initial items. However, that init function must return an object of the required type. With the above function signature, you only limit the upper type bound of T implicitly to be Any?. As pointed out by yourself, using Any() does not work, because it may not be a subtype of T; e.g. when T is Int, Any is not a subtype of Int - in fact it's the other way around.

One way around this, is to provide an init function to the transpose function, this way you can return objects of the required type on call site.

inline fun <reified T> transpose(xs: Array<Array<T>>, init: (index: Int) -> T): Array<Array<T>>

Then you may use this init function to create your Array.

val ys: Array<Array<T>> = Array(cols) { Array(rows) { init(it) } }