[GHC] #667: Efficient Map <-> Set conversions

#667: Efficient Map <-> Set conversions
--------------------------------+-------------------------------------------
    Reporter:  jpbernardy       |        Owner:              
        Type:  feature request  |       Status:  new         
    Priority:  normal           |    Milestone:              
   Component:  libraries/base   |      Version:  6.4.1       
    Severity:  normal           |     Keywords:  Data Map Set
          Os:  Unknown          |   Difficulty:  Unknown     
Architecture:  Unknown          |  
--------------------------------+-------------------------------------------
>> i propose the following class hierarchy:
 >>
 >> Collection
 >>   Sequential (lists, arrays)
 >>     UpdatableSequential (updatable arrays)
 >>   NonSequentional
 >>     KeyVal (AVLTree, Map)
 >>       UpdatableKeyVal (HashTable)
 >>     KeyOnly (Set)
 >>       UpdatableKeyOnly

 JPB> If anything, arrays can be seen as a KeyVal map too... We don't
 JPB> necessarily want a tree-like hierarchy. In any case, please post your
 JPB> suggestions on the list, preferably with the corresponding source
 JPB> code. The problem is not straightforward, and we certainly want to
 JPB> hear a few more opinions before deciding anything. ;)

 well, i am as user of libraries just wants consistency of using
 different data structures for the same tasks. for example, i want to
 have one indexing operator instead of !, !! and find. so, it's my
 hope-list:

 1) all collections are divided into 3-4 classes: arrays/lists, maps
 and sets. arrays/lists have sequential indexes in some range while
 maps have sparse indexes. also each class have an Updatable subclass

 2) collections in one class can be collected to each other with one
 (better universal) operator, such as:

 let list = cvt array
 let tree = cvt map

 3) collections can be converted to/from Updatable subclass with help
 of usual freeze/thaw operators

 4) all operations which are currently implemented in Data.List,
 Array.*, Map, Set, HashTable modules must be bound to one of these
 classes, with duplicates (such as !/!!) removed. now i see the
 following class hierarchy:

 Collection (map, size, values)
   SetLike (union, diff)
     Set
     Map
   Indexed (indexes, !)
     Map
     Sequential (reverse, head)
       Array
       List (tail)

 i give in parentheses examples of operations which are supported on
 each level of hierarchy


 this will give possibility to write datastructure-independent
 algorithms and easily convert data to the data type which are best
 for each part of the program, smthg like:

 a :: Map Int String <- read str
 algorithm1 a
 let b :: Hash Int String <- cvt a
 algorithm2 b
 c :: HashTable Int String <- thaw b
 algorithm3 c

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/667>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler_______________________________________________
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@xxxxxxxxxxx
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs