Hi Mark,
at the end of section 2 of http://www.cse.ogi.edu/~mpj/fds.html you
might want to mention that there is a "standard" work-around whenever a
type constructor is needed but not available: Introduce a newtype.
> import Bits
> class Collects e c where
> empty :: c e
> insert :: e -> c e -> c e
> member :: e -> c e -> Bool
> instance Eq e => Collects e [] where
> empty = []
> insert = (:)
> member = elem
Apply the work-around for characteristic functions.
> newtype CharacteristicFunction e = CF {unCF :: e -> Bool}
>
> instance Eq e => Collects e CharacteristicFunction where
> empty = CF (\y -> False)
> insert x c = CF (\y -> x == y || unCF c x)
> member x c = unCF c x
Apply the work-around for bit sets. The dummy type variable "a" is
needed to make "BitSet b" a type constructor. (I've also generalized
your example from Char to Enum.)
> newtype Bits b => BitSet b a = BS {unBS :: b}
>
> instance (Enum e, Bits b) => Collects e (BitSet b) where
> empty = BS (bit 0)
> insert x c = BS (setBit (unBS c) (fromEnum x))
> member x c = testBit (unBS c) (fromEnum x)
For the hash-table example I am pretty sure that the work-around works
as well, even though I could not figure out your intended
implementation.
Of course this is just a work-around and does not make functional
dependencies superfluous.
Regards,
Heribert.
