Open
Description
I noticed that the distinct implementations in cats data types are using on Scala's TreeSet
and the Order
typeclass. But what about a purely functional set based on Eq
using only boolean logic?
Upsides:
- Intuitively more performant than TreeSet, with O(1) lookup and insert
- Small memory footprint per object, so far just a case class
- Uses Eq instead of Order or Hash, which is closest to the mathematical definition of Set semantics
- Could give rise to a Predicate data type for cats as well, similar to the one seen in Haskell docs (http://hackage.haskell.org/package/contravariant-1.5/docs/Data-Functor-Contravariant.html)
Downsides:
- Ironically, could not derive an Eq instance for the set itself since it's based on a function?
- GC pressure due to copying of case classes
- No way to inspect elements, since it is only optimized for checking containment
- No way to check size
I wrote up a basic implementation (https://gist.github.com/nasadorian/8f10cc1f89225a932238026cf46e57a7) using just a case class and Eq
.
Would like to improve it and use more lawful constructs - I am thinking a better impl could depend on some Contravariant Functor like Predicate
since it is "containing" a function, but I'm not totally sure how to make that work.
The Set itself could have Monoid and Semigroup instances easily. I would also like to figure out if it's possible to make it a Functor.
Cheers!
Metadata
Metadata
Assignees
Labels
No labels