I'm facing a simple task, but struggle to solve it elegantly. (To clarify: performance is not an iss...

# arrow

[Bart Kleijngeld]

I'm facing a simple task, but struggle to solve it elegantly. (To clarify: performance is not an issue).

I have two Set<X> collections, and I want to see if they contain equal items. The challenge is that this equality must be tested by some external isomorphic function (which takes two arguments of type X) instead of the standard equality operator.

Can someone point towards helpful ideas or tools in Kotlin/Arrow?

[Bart Kleijngeld]

My initial idea was to have a Cartesian product which I zip, and then I can use all to force equality by the isomorphic function.

I'm not sure if that's the best option though. Moreover, I can't seem to find anything in Arrow or Kotlin to perform a Cartesian product (like Python's itertools.product)

[Robert Menke]

So you want to see if there’s a 1:1 mapping between all items of set A and set B? For example

True
A: 1, 2, 3
B: 3, 1, 2

False:
A: 1, 2, 3
B: 2, 3, 4

[Bart Kleijngeld]

Exactly. But to emphasize: equality among elements should be tested using the function isomorphic, not ==.

[Robert Menke]

Is that a function provided by arrow? I’m out of the loop

[Bart Kleijngeld]

No, it's from the 3rd party library I'm working with. Its inner workings shouldn't matter, all you should need to know is that it returns true if it deems two elements equal, and false otherwise

[Robert Menke]

Are the sets sorted?

[Bart Kleijngeld]

Sets are unordered by definition, and for reasons tied to my use case you can assume no ordering is possible, so there's no possibility of (usefully) casting to some ordered collection type (like List)

[Bart Kleijngeld]

I seemed to have found one way of doing it which seems okay only works if A is a subset of B , so that doesn't suffice, but:

setA.all { a -> setB.any { b -> isomorphic(a, b) } }  // should be true

[Robert Menke]

I think for an unordered set that’s the time complexity you’re stuck with.

[Bart Kleijngeld]

Yes, probably so. I should note that performance is not an issue here though. It's really just a handful of elements in each set.

[Robert Menke]

Ahh ok that’s good to know

[Robert Menke]

If set B has elements that set A doesn’t have is that ok?

[Robert Menke]

I don’t think that implementation would capture that

[Bart Kleijngeld]

You're right. Thanks for catching that

[Robert Menke]

I also don’t have my set theory vocabulary down so I may be wrong here but I think the right word for what you’re trying to determine is if the sets are injective

[Robert Menke]

Might need to end up with something like this

fun <T> Set<T>.containsAllIsomorphic(other: Set<T>) = this.all { a -> other.any { b -> isomorphic(a, b)} }
fun <T> Set<T>.isInjective(other: Set<T>) = this.containsAll(other) && other.containsAll(this)

[Robert Menke]

Bad performance for large sets, but when data is small no big deal 🙂

[Bart Kleijngeld]

Yes, that would work. I'm really hoping there's a nicer way than this, although it wouldn't be too bad.

[Bart Kleijngeld]

Thanks for your help!

[Robert Menke]

Anytime 🙂

[Bart Kleijngeld]

One small improvement: instead of checking both sides, you can also check one side and make sure both sets have the same amount of elements.

[Robert Menke]

True that would be smarter 🙂