Map, Set

Serge D. Mechveliani mechvel at
Fri Jun 3 03:20:42 EDT 2005

On 2 Jun 2005  S. Alexander Jacobson <alex at>

> Any reason the libaries don't define:
>   class HasNull a where null::a->Bool
>   class HasEmpty a where empty::a
> I find that I sometimes switch between using lists, sets, or tables as 
> my collection type and the forced import qualifification for generic 
> collection operations seems annoying.

Probably, it would be natural for the  Map and Set GHC libraries  to 
introduce some version of  
                          class SetLike where ...

My programs also switch with similar operations between sets and 
various tables.
To unify the interface, I defined the following:

  class Cardinality a where  card :: a -> Natural      -- (Integer)

  instance Cardinality (Set.Set a) where
                                   card = genericLength . Set.elems
  instance Cardinality (Map.Map k a) where
                                     card = genericLength . Map.keys

  class Cardinality a => SetLike a where sEmpty     :: a
                                         sIsEmpty   :: a -> Bool
                                         sUnion     :: [a] -> a
                                         sMinus     :: a -> a -> a
                                         sIntersect :: [a] -> a
                                         sConcat    :: [a] -> a
                                         sNub       :: a -> a
  instance Ord a => SetLike (Set.Set a)
    sEmpty   = Set.empty
    sIsEmpty = Set.null
    sUnion   = Set.unions
    sMinus   = Set.difference
    sNub     = id
    sConcat  = sUnion

    sIntersect []     = error "sIntersect []\n"
    sIntersect (s:ss) = foldl Set.intersection s ss

  sIncluded :: SetLike a => a -> a -> Bool
  sIncluded                 s =  sIsEmpty . sMinus s

  instance SetLike IdList where 

This was as under  ghc-6.2.2,  and now it is edited to meet  6.4.

About what Set and Map libraries could provide
The candidates may be

  `any', `all'  analogues for Set, Map 
         (anyway, they are simply expressed by composing with  toList).

  direct product  of sets  
         (can be simply expressed by composing with  toList, fromList).

  composition of maps,  inverse map.

On standard
It is very desirable to put the Map and Set libraries to future 
standard Haskell library. With this, our struggle with their interface 
changes will end. 
I wonder how the Haskell language and library are going on, whether 
Haskell-2 is coming.


Serge Mechveliani
mechvel at

More information about the Glasgow-haskell-users mailing list