[Haskell-cafe] Sets, typeclasses and functional dependencies

Henning Thielemann lemming at henning-thielemann.de
Sat Jul 31 09:14:29 UTC 2021

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

More information about the Haskell-Cafe mailing list