[Haskell-cafe] Sets, typeclasses and functional dependencies

[Richard O'Keefe]

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 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,
>
> 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.