https://kotlinlang.org logo
Join Slack
Powered by
Hello all, just a quick question, I wonder if such...
# functional
t
Hello all, just a quick question, I wonder if such a function exists in the Kotlin standard library? if not how should it be named? I'm calling it "combine" for now 🤔
Copy code
fun <A, B, R> Collection<A>.combine(other: Collection<B>, transformation:(A, B)->R): List<R> = 
    ArrayList<R>(this.size * other.size).also{
        for(a in this){
            for(b in other){
                it.add(transformation(a, b))
        	}
        }
    }
Example:
Copy code
fun main(){
   println( 
       listOf(1,2,3).combine(listOf("a", "b", "c")){a, b -> "$a-$b"} 
   )
}
Output:
Copy code
[1-a, 1-b, 1-c, 2-a, 2-b, 2-c, 3-a, 3-b, 3-c]
e
it doesn't exist, but it could be more concisely written
Copy code
fun <A, B, R> Iterable<A>.cartesianProduct(other: Iterable<B>, transform: (A, B) -> R): Iterable<R> =
    this.flatMap { a -> other.map { b -> transform(a, b) } }
👍 1
t
Thanks for the quick response! To be honest I dislike the use of 
flatMap
, for me it is like using FP for the sake of using FP. A nested for loop is dead simple, to the point, with guaranteed good performance 🤔 Implementing the extension function on 
Iterable
seems like a good idea too but since 
Iterables
has no size it might involve resizing the result list
ah and I just noticed that you named the transformation parameter 
transform
, which follows the Kotlin convention, its a nice touch too
e
even if you wanted to avoid intermediate allocations and resizing, I'd still use 
buildList
instead of 
ArrayList
Copy code
fun <A, B, R> Iterable<A>.cartesianProduct(other: Iterable<B>, transform: (A, B) -> R): List<R> =
    buildList(if (this is Collection<*> && other is Collection<*>) this.size * other.size else 0) {
        for (a in this@cartesianProduct) other.mapTo(this) { b -> f(a, b) }
    }
t
whats the issue with 
ArrayList
may I ask?
e
I see a feature request https://youtrack.jetbrains.com/issue/KT-25015/Cartesian-product-of-two-Lists-Sequences-Iterables but ultimately it's probably not used often enough to end up in stdlib
👀 1
👍 1
d
Not quite sure I understand why you dislike 
flatMap
. As for the intermediate allocations, it usually shouldn't be too bad, as the array sizing is amortized to 
O(1)
average time.
👀 1
t
It's mostly because I find the nested for loop approach simpler than the 
flatMap
+ 
map
approach. To say that something is "not too bad" is to imply that it is not optimal, while I don't see anything to optimize with the nested for loop approach.
d
I personally tend to find 
for
loops less clear than 
map
or even 
forEach
, but that might be more of a taste thing. I also spend more time trying to make sure my code is correct and clear, than making sure I micro-optimize a non critical section.
Event GitHub Copilot suggests the flatMap+map approach:
Copy code
// cartesian product of two iterables
fun <T, U, R> Iterable<T>.cartesianProduct(other: Iterable<U>, transform: (T, U) -> R): List<R> =
    flatMap { t -> other.map { u -> transform(t, u) } }
What I like about this code is that I don't have to comprehend "iterating over stuff and adding results to a collection, then returning that collection". Instead, I'm able to immediate see "transform the elements in the collection". It's a minor thing in the grand scheme, but it ultimately saves me some cognitive load.
t
Most of the implementations in 
Collections.kt
from stdlib would use 
for
loops instead of generic higher-order functions
Well yeah you've got a a good point on cognitive load
I think I'm fine with this:
Copy code
inline fun <T, U, R> Iterable<T>.cartesianProduct(other: Iterable<U>, transform: (T, U) -> R): List<R> =
    buildList {
        for (t in this@cartesianProduct) {
            for (u in other) {
                add(transform(t, u))
            }
        }
    }

inline fun <T, U, R> Collection<T>.cartesianProduct(other: Collection<U>, transform: (T, U) -> R): List<R> =
    buildList(this.size * other.size) {
        for (t in this@cartesianProduct) {
            for (u in other) {
                add(transform(t, u))
            }
        }
    }

inline fun <T, U> Collection<T>.cartesianProduct(other: Iterable<U>): List<Pair<T, U>> =
    this.cartesianProduct(other, ::Pair)

inline fun <T, U> Iterable<T>.cartesianProduct(other: Iterable<U>): List<Pair<T, U>> =
    this.cartesianProduct(other, ::Pair)
Thanks again for all the replies!
d
I personally also like sequences, so I would add a sequence version which also returns a sequence.
👍 1
t
ahh yes and arrays too... typed arrays and primitive arrays
never mind I'm too lazy for this 🫠
d
lol
I just recently started using Github CoPilot at work, and it does so much of this tedious stuff for me now. It still gets things wrong occasionally, so I still need to think and understand it, but I'm surprised how helpful it can be.
It just spit all of this out for me:
Copy code
fun <T, U, R> Sequence<T>.cartesianProduct(other: Sequence<U>, transform: (T, U) -> R): Sequence<R> =
    sequence {
        for (t in this@cartesianProduct) {
            for (u in other) {
                yield(transform(t, u))
            }
        }
    }

fun <T, U> Sequence<T>.cartesianProduct(other: Sequence<U>): Sequence<Pair<T, U>> =
    cartesianProduct(other) { t, u -> t to u }

fun <T, U, R> Iterable<T>.cartesianProduct(other: Iterable<U>, transform: (T, U) -> R): Sequence<R> =
    asSequence().cartesianProduct(other.asSequence(), transform)

fun <T, U> Iterable<T>.cartesianProduct(other: Iterable<U>): Sequence<Pair<T, U>> =
    asSequence().cartesianProduct(other.asSequence())

fun <T, U, R> Array<T>.cartesianProduct(other: Array<U>, transform: (T, U) -> R): Sequence<R> =
    asSequence().cartesianProduct(other.asSequence(), transform)

fun <T, U> Array<T>.cartesianProduct(other: Array<U>): Sequence<Pair<T, U>> =
    asSequence().cartesianProduct(other.asSequence())

fun <T, U, R> Sequence<T>.cartesianProduct(other: Iterable<U>, transform: (T, U) -> R): Sequence<R> =
    cartesianProduct(other.asSequence(), transform)

fun <T, U> Sequence<T>.cartesianProduct(other: Iterable<U>): Sequence<Pair<T, U>> =
    cartesianProduct(other.asSequence())

fun <T, U, R> Iterable<T>.cartesianProduct(other: Sequence<U>, transform: (T, U) -> R): Sequence<R> =
    asSequence().cartesianProduct(other, transform)

fun <T, U> Iterable<T>.cartesianProduct(other: Sequence<U>): Sequence<Pair<T, U>> =
    asSequence().cartesianProduct(other)

fun <T, U, R> Array<T>.cartesianProduct(other: Iterable<U>, transform: (T, U) -> R): Sequence<R> =
    asSequence().cartesianProduct(other.asSequence(), transform)

fun <T, U> Array<T>.cartesianProduct(other: Iterable<U>): Sequence<Pair<T, U>> =
    asSequence().cartesianProduct(other.asSequence())

fun <T, U, R> Sequence<T>.cartesianProduct(other: Array<U>, transform: (T, U) -> R): Sequence<R> =
    cartesianProduct(other.asSequence(), transform)

fun <T, U> Sequence<T>.cartesianProduct(other: Array<U>): Sequence<Pair<T, U>> =
    cartesianProduct(other.asSequence())

fun <T, U, R> Iterable<T>.cartesianProduct(other: Array<U>, transform: (T, U) -> R): Sequence<R> =
    asSequence().cartesianProduct(other.asSequence(), transform)

fun <T, U> Iterable<T>.cartesianProduct(other: Array<U>): Sequence<Pair<T, U>> =
    asSequence().cartesianProduct(other.asSequence())

fun <T, U, R> Array<T>.cartesianProduct(other: Sequence<U>, transform: (T, U) -> R): Sequence<R> =
    asSequence().cartesianProduct(other, transform)

fun <T, U> Array<T>.cartesianProduct(other: Sequence<U>): Sequence<Pair<T, U>> =
    asSequence().cartesianProduct(other)
t
woah that looks really convenient
I have never tried copilot
d
Yeah, and if I don't like what its doing, I can rewrite part of it, and it tends to understand the difference in intent and follow the new pattern.
t
yeah check out all those 
asSequence()
calls haha
d
Yeah, but if I wanted to do it your way, I could write that one first and see if it figures out the rest...
It also didn't make them inline.
In any case, it isn't a silver bullet, but I was surprised how helpful it could be. Good luck with your project 😉
🙂 1
👍 1
e
k
Going back several responses, Thomas, you've overloaded the function on 
Iterable
and 
Collection
, with the latter using a more efficient way to build the list by avoiding reallocations. This is not ideal. An object can be 
Iterable
at compile time and 
Collection
at runtime. For example:
Copy code
listOf(1, 2, 3).asIterable().cartesianProduct(listOf('a', 'b').asIterable())
This would make the compiler call the 
Iterable
version of your function, even though its arguments are actually 
Collection
. It might be better to check the type at runtime (
if (this is Collection<*>)
) even though that check itself incurs a slight runtime overhead.
t
From the perspective of user of the function, the moment they decide to call the first 
asIterable()
, they must have made a decision and accepted that information will be lost. This is because calling 
asIterable()
from a 
List
is clearly an upcasting action, losing information from upcasting is inevitable 🤔
plus1 2
18 Views
Open in Slack
PreviousNext
Powered by