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

[GHC]

#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                    |     Resolution:         
  Keywords:  Data Map Set collections  |             Os:  Unknown
Difficulty:  Unknown                   |   Architecture:  Unknown
---------------------------------------+------------------------------------
Old description:

> >> 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

New description:

 We should be able to convert a Set into a Map without re-computation of
 the tree Shape. (initially proposed by John Meacham)

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/667>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler