[Haskell-cafe] Sets, typeclasses and functional dependencies
raoknz at gmail.com
Mon Aug 2 02:29:11 UTC 2021
The thing about powerset is that it is great for reasoning and as a
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
On Sat, 31 Jul 2021 at 22:15, Stuart Hungerford
<stuart.hungerford at gmail.com> wrote:
> On Sat, Jul 31, 2021 at 7:14 PM Henning Thielemann
> <lemming at 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,
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> Only members subscribed via the mailman list are allowed to post.
More information about the Haskell-Cafe