https://kotlinlang.org logo
Title
d

David Kubecka

03/24/2023, 9:55 AM
Is there any way how to partition a list using an isInstance predicate, so that the matching elements are of the given type?
val (xs, nonXs) = list.partition { it is X }
// xs is of type List<X>
w

Wout Werkman

03/24/2023, 9:56 AM
The standard library doesn't have such function. You'd have to create such utility functions yourself
d

David Kubecka

03/24/2023, 9:59 AM
And what would be the easiest/most idiomatic way? Using partition and then casting (unsafely)?
w

Wout Werkman

03/24/2023, 10:02 AM
Yeah, I'd say that's an okay approach. You could circumvent the unsafe cast by manually creating 2 lists, but I think a cast is fine here.
Less idiomatic code is totally fine if it's isolated inside a small* function with a good signature.
d

David Kubecka

03/24/2023, 10:06 AM
agree 👍
s

Stephan Schröder

03/24/2023, 2:30 PM
here my solution which avoids unsafe casting and only iterates through each element exactly onces:
inline fun <A,reified B: A> List<A>.partitionIsInstance(): Pair<List<A>, List<B>> {
    val aList = ArrayList<A>(this.size)
    val bList = ArrayList<B>(this.size)
    this.forEach {
        if (it is B) {
            bList.add(it)
        } else {
            aList.add(it)
        }
    }
    return aList to bList
}
unfortunately, the compiler isn't smart enough to deduce the types correctly from
val instances: List<AC> = listOf(AC(), AC(), BC(), AC(), BC() )
val (aList: List<AC>, bList: List<BC>) = instances.partitionIsInstance()
so you have to add the types to the invocation:
val (aList: List<AC>, bList: List<BC>) = instances.partitionIsInstance<AC, BC>()
here's the playground link to play around with it: https://pl.kotl.in/RDbthQSqO
j

Joffrey

03/24/2023, 2:33 PM
If you're ok with looping twice on the list, you could also use
filterIsInstance<X>()
twice. But if you need this more often, something like what Stephan suggested would indeed be better
@Stephan Schröder I'd rather invert the returned pair. I think
partition
returns first the true elements and then the false ones
s

Stephan Schröder

03/24/2023, 2:43 PM
@Joffrey David can adept the code, if he wants to 🤷‍♂️ @David Kubecka if your initial list is mutable and you're fine with a modifying operation you can use
inline fun <A,reified B: A> MutableList<A>.extractSubclass(): List<B> {
    val bList = ArrayList<B>(this.size)
    this.forEach {
        if (it is B) {
            bList.add(it)
        }
    }
    this.removeAll(bList)
    return bList
}
afterwards your initial list only has the instances which weren't the specific subclass. Also type inference is smarter now:
val instances: MutableList<AC> = mutableListOf(AC(), AC(), BC(), AC(), BC() )
val bList: List<BC> = instances.extractSubclass()
try it out here: https://pl.kotl.in/EflE6GJPZ
actually now the code gets shorter when using
isInstance
😅
inline fun <A,reified B: A> MutableList<A>.extractSubclass(): List<B> {
    val bList = this.filterIsInstance<B>()
    this.removeAll(bList)
    return bList
}
d

David Kubecka

03/24/2023, 2:48 PM
@Stephan Schröder I usually try to avoid mutability but thanks for the option 🙂
you could also use
filterIsInstance<X>()
twice.
Yeah, that's actually what I'm currently doing. But the explicit cast (especially if nicely encapsulated) is IMO worth the peace of mind that single pass algorithm provides 😅
s

Stephan Schröder

03/24/2023, 2:51 PM
and in the spirit of always trying to get a single statement form of a function even though it's the version on MutableList:
inline fun <A,reified B: A> MutableList<A>.extractSubclass(): List<B> = this.filterIsInstance<B>().also {this.removeAll(it)}
d

David Kubecka

03/24/2023, 2:55 PM
The original single-pass version by @Stephan Schröder is interesting. I wonder though if we can somehow get rid of specifying both generic parameters as in
instances.partitionIsInstance<AC, BC>()
. The
AC
can be derived from the context (
instances
) so I would rather want it to be used as
instances.partitionIsInstance<BC>()
. The ease of use is probably my main acceptance criterion for such a utility function.
s

Stephan Schröder

03/24/2023, 2:57 PM
I played around with it, but wasn't able to even drop the
AC
part, not even in 1.8.20-RC. I was slightly disappointed as well.
d

David Kubecka

03/24/2023, 3:01 PM
Interesting. This looks like a general opportunity for compiler improvement. If I understand it right the problem is that while the compiler can deduce the type for single param methods such as
fun <T> List<T>.first(...)
it has trouble doing so partially for more params. Do you think this is worth reporting? Or perhaps it's already reported?
s

Stephan Schröder

03/24/2023, 3:02 PM
another slower but space-saving optimization I thought about was initialising both lists with half the capacity. One of the list will need to be copied over to a bigger backing array, but the smaller list wastes less space.
val aList = ArrayList<A>(this.size/2)
    val bList = ArrayList<B>(this.size/2)
Not something I normally thing about in a GC-language 😅
@David Kubecka it would be nice if Kotlin2.0 would support this. better smart casts is on the agenda.
d

David Kubecka

03/24/2023, 3:07 PM
Nitpick: I think this is technically not a smart cast but rather a type inference 🤯
w

Wout Werkman

03/24/2023, 3:12 PM
Just to finish our thought experiment, I do not post this because I recommend writing this, but wanted to share this rather wonky method of actually allowing Kotlin to infer the first generic parameter.
And if you write it like this it even has the same performance and allocations as the initial approach
e

ephemient

03/24/2023, 6:17 PM
you could more generally write
inline fun <T, R : Any> Iterable<T>.mapNotNullAndPartition(transform: (T) -> R?): Pair<List<R>, List<T>> {
    val mapped = mutableListOf<R>()
    val unmapped = mutableListOf<T>()
    for (elem in this) {
        transform(elem)?.let { mapped.add(it) } ?: unmapped.add(elem)
    }
    return mapped to unmapped
}

val (xs, nonXs) = list.mapNotNullAndPartition { it as? X }
if this is a recurring pattern
d

David Kubecka

03/24/2023, 7:31 PM
Isn't this basically the same as the original version of partitionIsInstance by @Stephan Schröder workarounding (in a clever way) the compiler deficiency we spoke about earlier? I mean if the compiler could infer the types why would anyone prefer this version ?
e

ephemient

03/24/2023, 7:33 PM
it's more general: you could write
.mapNotNullAndPartition { it.toIntOrNull() }
for example
and I'd be happy to be proven wrong by a viable design, but I don't see any sane way to get the compiler to infer the types
we'd need contracts with subtyping at the least
d

David Kubecka

03/24/2023, 7:37 PM
You mean that with
inline fun <A,reified B: A> List<A>.partitionIsInstance()
and a concrete call
List<Int>.partitionIsInstance()
there's no way that the compiler could infer that A is Int?
Of course you would have to still specify B.
e

ephemient

03/24/2023, 7:38 PM
I mean with the original
partition
function taking a predicate
d

David Kubecka

03/24/2023, 7:38 PM
Yeah, that one is clear and I wouldn't expect that. I was just asking the question to stir the discussion 🙂