[Haskell-cafe] Sets, typeclasses and functional dependencies

[Henning Thielemann]

On Sat, 31 Jul 2021, Stuart Hungerford wrote:

> I can see why Haskell base does not provide typeclasses for sets. I'm
> wondering now though if I did create a Set typeclass what it would
> look like. There's several approaches using various language
> extensions and to me this approach using functional dependencies seems
> simpler than the other approaches:
>
> class Setish set a | set -> a where
>
>  empty :: set
>
>  singleton :: a -> set
>
>  -- and so on.

A more modern approach would use type functions:

class Setish set where
   type Element set
   empty :: set
   singleton :: Element set -> set

> 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]

If you want that the powerset type is determined by the set type, then you 
might define

class Settish set where
    ...
    type Powerset set
    powerset :: set -> Powerset set