Disjoint-Set about cats-collections HOT 5 CLOSED

Hi @lewismj , I was about to open the a PR with the functionality for disjoint sets when I found yours. I wanted to bring into dogs the implementation I published at
https://github.com/pfcoperez/algorithmaday/tree/master/src/main/scala/org/pfcoperez/dailyalgorithm/datastructures/sets

Which is a pure functional version of the structure described at CLRS. I implemented it in Python in 2012 and provided an small summary of the structure described by Thomas Cormen.

Few days ago I adapted it to a pure functional implementation.
In fact I also provided a state monad set of operation thus making it able to be used using for notation in such a way that the state propagation is transparent for the user:

The point is that I was reviewing your implementation and I see it's simple, it implements union by rank heuristic as well. However it seems to lack the path compression heuristic. That is OK for most cases but it can lead to degraded states where lookups can be as slow as O(n), n = max depth. Check the how the tree depth increases in this example where the path compression is not being applied:

I hope you don't mind if open a PR with my version so we can discuss the differences.

from cats-collections.

Looks good, I thought about implementing the path compression (I mentioned it in the code comment), but decided not to in the end. It was partly because I wanted to avoid bringing in a dependency like Cats or roll my own Monad. I wan't sure about bringing in a dependency on Cats of if dogs had to be standalone... I couldn't decide in the end if it was worth doing or not (edit: I think in the end, and it was personal, it was better to keep a slightly simpler codebase)

from cats-collections.

Hi @lewismj , the implementation at https://github.com/pfcoperez/algorithmaday/blob/master/src/main/scala/org/pfcoperez/dailyalgorithm/datastructures/sets/DisjointSets.scala doesn't use Cats, it follows a standalone approach as you suggested, it is curious that we share the same criteria in that regards 😄

It has a wrapper to make it "Cats friendly": https://github.com/pfcoperez/algorithmaday/blob/master/src/main/scala/org/pfcoperez/dailyalgorithm/datastructures/sets/MonadicDisjointSets.scala

Not implementing one of the heuristics might be enough, there are some corner cases leading to the need of path compression. Nevertheless, I fear that path compression is required to keep time complexity bounds.

I've already created a PR (#90) with an implementation including path compression.

Nice relatively unknown data structure, isn't it?

from cats-collections.

This has been already merged.

from cats-collections.

Thanks!

from cats-collections.