Changes between Version 5 and Version 6 of CollectionLibraries


Ignore:
Timestamp:
Jan 28, 2006 12:27:18 PM (8 years ago)
Author:
jpbernardy
Comment:

Imported content from the other wiki.

Legend:

Unmodified
Added
Removed
Modified
  • CollectionLibraries

    v5 v6  
     1= Standard Collection Libraries = 
     2 
     3== Mission Statement == 
     4 
     5Provide the Haskell language a reliable, stable, coherent, efficient, function-rich collections library. 
     6 
     7 1. Reliable: As few bugs as possible. This also implies the next goal, stability. 
     8 1. Stable:  
     9    * The API should change as rarely as possible. API changes must be backward compatible. 
     10    * Changes in the behaviour should be rare as well, and for the generally-agreed better. 
     11 
     12 1. Coherent: both behaviour and APIs should be coherent across the libraries, in order not to confuse the user. 
     13 1. Efficient, feature-rich: Apart from the obvious, this means that more than one implementation will be needed in the long run. 
     14 
     15== Related Tickets == 
     16 
    117 * [/trac/ghc/newticket?version=6.4.1&keywords=collections&component=libraries/base&type=bug Create a new bug report] 
    218 * [/trac/ghc/newticket?version=6.4.1&keywords=collections&component=libraries/base&type=task Create a new task] 
     
    622 * [query:?keywords=~collections&component=libraries/base&status=new&status=assigned&status=reopened&type=task&order=priority&group=difficulty View tasks] 
    723 * [query:?keywords=~collections&component=libraries/base&status=new&status=assigned&status=reopened&type=feature+request&order=priority View feature requests] 
     24 
     25== API and policies == 
     26 
     27=== Module-level API === 
     28 
     29The existing Data.Map and Data.Set define a de-facto API. This API is important because many existing haskell programs use it. (See the corresponding haddock documentation for a "definition" of the API.) 
     30 
     31Implementors of alternatives to Data.Map and Data.Set are advised to stick as closely as reasonably possible to the existing API. This would allow users to switch between implementations by just changing their import directive. 
     32 
     33However, there are legitimate reasons not to strictly stick to the same interface. Should an implementor choose to do so, minor changes, or not-misleading changes, should be considered first. For example: 
     34 
     35 * Drop a function 
     36 * Change the context (constraints) of a function type 
     37 * Harmless changes in behaviour (ie. different asymptotic performance) 
     38 
     39A important case, discussed at length in the mailing list, concerns left-biasing in Sets and key-sets of Maps in the presence of non-structural equality. Assuming structural equality (or not enforcing the left-bias) is considered a minor change, because few people actually rely on it in their programs. 
     40 
     41Misleading changes are strongly discouraged: 
     42 
     43 * Changing the type of a function, besides the constraints. 
     44 * Reusing a name for a different purpose 
     45 * Using a different name for the same purpose 
     46 
     47=== Class-based API === 
     48 
     49The definition of a set of classes for collection types is in progress. 
     50See the CollectionClassFramework for details. 
     51 
     52== Work done == 
     53 
     54 * Standardized testing framework.  
     55   * Checks correctness of the libraries. 
     56   * The same is used independantly of the element types. 
     57 
     58== Short terms plans == 
     59 
     60 * Have a consistent performance checker. 
     61  
     62== Long term plans & ideas == 
     63  
     64 * Gather alternative collection implementations. Those must pass the regression tests. Note that this implies that they conform to the naming conventions already in place. 
     65 Candidates for inclusion: 
     66  * Adrian Hey's AVL trees 
     67  * Tries 
     68  * ... 
     69 * Develop a convenient class framework to accomodate most day-to-day usage of collection types. 
     70  * Use AVL trees implementation as default 
     71 * Performance tests should compute the complexity bounds automatically.