[Haskell-cafe] Sets, typeclasses and functional dependencies

[Stuart Hungerford]

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