Map, Set

[Serge D. Mechveliani]

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

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

Regards,

-----------------
Serge Mechveliani
mechvel at botik.ru