Re: [Haskell-cafe] Sets, typeclasses and functional dependencies

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 wrote:

On Sat, Jul 31, 2021 at 7:14 PM Henning Thielemann 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.