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