[GHC] #666: Collection hierarchy proposal

[GHC]

#666: Collection hierarchy proposal
-------------------------------+--------------------------------------------
  Reporter:  jpbernardy        |          Owner:  jpbernardy
      Type:  feature request   |         Status:  new       
  Priority:  normal            |      Milestone:            
 Component:  libraries/base    |        Version:  6.4.1     
  Severity:  normal            |     Resolution:            
  Keywords:  Data collections  |             Os:  Unknown   
Difficulty:  Unknown           |   Architecture:  Unknown   
-------------------------------+--------------------------------------------
Changes (by jpbernardy):

  * owner:  => jpbernardy

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:

 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/666>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler