Is there any way how to partition a list using an ...

# getting-started

[David Kubecka]

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>

[Wout Werkman]

The standard library doesn't have such function. You'd have to create such utility functions yourself

[David Kubecka]

And what would be the easiest/most idiomatic way? Using partition and then casting (unsafely)?

[Wout Werkman]

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.

[Wout Werkman]

Less idiomatic code is totally fine if it's isolated inside a small* function with a good signature.

[David Kubecka]

agree 👍

[Stephan Schröder]

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

[Joffrey]

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

[Joffrey]

@Stephan Schröder I'd rather invert the returned pair. I think partition returns first the true elements and then the false ones

[Stephan Schröder]

@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

[Stephan Schröder]

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
}

[David Kubecka]

@Stephan Schröder I usually try to avoid mutability but thanks for the option 🙂

[David Kubecka]

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 😅

[Stephan Schröder]

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

[David Kubecka]

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.

[Stephan Schröder]

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.

[David Kubecka]

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?

[Stephan Schröder]

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 😅

[Stephan Schröder]

@David Kubecka it would be nice if Kotlin2.0 would support this. better smart casts is on the agenda.

[David Kubecka]

Nitpick: I think this is technically not a smart cast but rather a type inference 🤯

[Wout Werkman]

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.

[Wout Werkman]

And if you write it like this it even has the same performance and allocations as the initial approach

[ephemient]

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

[David Kubecka]

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 ?

[ephemient]

it's more general: you could write .mapNotNullAndPartition { it.toIntOrNull() } for example

[ephemient]

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

[ephemient]

we'd need contracts with subtyping at the least

[David Kubecka]

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?

[David Kubecka]

Of course you would have to still specify B.

[ephemient]

I mean with the original partition function taking a predicate

[David Kubecka]

Yeah, that one is clear and I wouldn't expect that. I was just asking the question to stir the discussion 🙂