The thing about powerset is that it is great for reasoning and as a starting point for a derivation, but horrible as a data structure. Power sets get very big very fast, and even in a lazy language, where you might not store an entire powerset, traversing one takes a lot of time. So it's seldom included in practical finite set implementations. On Sat, 31 Jul 2021 at 22:15, Stuart Hungerford <stuart.hungerford@gmail.com> wrote:
On Sat, Jul 31, 2021 at 7:14 PM Henning Thielemann <lemming@henning-thielemann.de> wrote:
[...] A more modern approach would use type functions:
class Setish set where type Element set empty :: set singleton :: Element set -> set
Thanks for the pointer.
My question is how does the functional dependency in Setish interact with "extra" types needed for richer set operations like finding the powerset or taking a cartesian product?
powerset would need a type like:
powerset :: (Powersettish powerset, Element powerset ~ set, Setish set) => set -> powerset
with an extra Powersettish class.
However, the type checker could not guess the exact powerset type, it could be, e.g. powerset :: Set a -> Set (Set a) or powerset :: Set a -> [Set a]
Okay, I'm starting to see why the "Set" typeclass examples I could find don't include a powerset or cartesian product method.
Thanks again,
Stu _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.