haskelltype-families

Data Family default instances


I want to use data families to create efficient Set representations for certain data types. For all other (Ord) data types, I want to use Data.Set as the instance. The catch is, I don't want to explicitly instantiate the data kind class with each type I want to use it with in this case. Instead I want a general instance that covers the remaining types.

Example:

{-# LANGUAGE TypeFamilies #-}

module Test where
    
import qualified Data.Set as D

class SetKey a where
    data Set a :: *
    empty :: Set a
    insert :: a -> Set a -> Set a
    member :: a -> Set a -> Bool
    toList :: Set a -> [a]
    
instance SetKey Bool where
    data Set Bool = BoolSet Bool Bool
    empty = BoolSet False False
    insert x (BoolSet t f) = case x of
        True -> BoolSet True f
        False -> BoolSet t True
    member x (BoolSet t f) = case x of
        True -> t
        False -> f
    toList (BoolSet t f) = if t && f
        then [True, False]
        else if t
            then [True]
            else if f
                then [False]
                else []

I know the following does not work without UndecidableInstances. Even still, this would cause conflicts with the Bool instance for SetKey (Bool is an instance of Ord)

instance (Ord a) => SetKey a where
    newtype Set a = Wrap { unWrap :: D.Set a }
    empty = Wrap . D.empty
    insert x = Wrap . D.insert x . unWrap
    member x = Wrap . D.member . unWrap
    toList = D.toList . unWrap

How would I go about resolving this kind of problem? I've tried putting defaults directly into the data family class definition, but either I cannot figure out the syntax or the functionality simply does not exist:

class SetKey a where
    data Set a :: *
    data Set a = D.Set a
    empty :: Set a
    empty = D.empty
    insert :: a -> Set a -> Set a
    insert = D.insert
    member :: a -> Set a -> Bool
    member = D.member
    toList :: Set a -> [a]
    toList = D.toList

If the code cannot ever work, what can I do instead? Could code like this work if Data.Set didn't have Ord requirements?


Solution

  • Default data families doesn't make sense, because you have to declare the constructors of the data type, and you can't have constructors with the same name for different types. You can't use a data family as a type family like you did in your last example.