Edison: A Library of Efficient Data Structures Version: 1.2.1 Dec 15, 2006 About Edison ----------------------- Edison is a library of purely function data structures for Haskell originally written by Chris Okasaki. Conceptually, it consists of two things: 1) A set of type classes defining data the following data structure abstractions: "sequences", "collections" and "associative collections" 2) Multiple concrete implementations of each of the abstractions. In theory, either component may be used independently of the other. This release is an update to (hopefully) make Edison easier to use, mostly by updating Edison to use the most current Haskell tools. The following major changes have been made since version 1.1, which was released in 1999. * Typeclasses updated to use fundeps (by Andrew Bromage) * Implementation of ternary search tries (by Andrew Bromage) * Modules renamed to use the hierarchical module extension * Documentation haddockized * Source moved to a darcs repository * Build system cabalized * Unit tests integrated into a single driver program which exercises all the concrete implementations shipped with Edison * Multiple additions to the APIs (mostly the associated collection API) Hopefully, these changes will make Edison more accessible than it has been previously. License ----------------------- Edison is released under an MIT style license. See the COPYRIGHT file for details. Building Edison ----------------------- Edison is distributed as a set of related Cabal packages. The EdisonAPI package contains the main API typeclass definitions. The EdisonCore package provides the main concrete implementations; this package depends on the EdisonAPI package. The Edison-test package contains the test suite and depends on both packages. You may either manually invoke cabal for each of the sub-packages as appropriate, or you may use the included Makefile, which will build and install the EdisonAPI and EdisonCore packages automaticly. If you do not have an executable named 'runhaskell' on your search path, you will need to edit the Makefile and set the RUNHS variable appropriately (or run the cabal commands manually). If you wish to build the API docs, you will first need to build the relevant package and type the following command in the package subdirectory: runhaskell Setup.hs haddock A Note about Cabal versions ----------------------------------- This version of edison builds correctly with Cabal version 1.1.4, which is shipped with GHC 6.4.2. To build on earlier versions, it should suffice to: s/UndecidableInstances/AllowUndecidableInstances/ s/Hs-Source-Dirs:/Hs-Source-Dir:/ in the .cabal files. Notes on portability ---------------------- Short version: Edison is expected to work correctly on recent GHC and Hugs (with extensions enabled). Other Haskell implementations may also work, but have not been tested. Longer version: Edison uses a number of extensions beyond Haskell 98, the current official Haskell standard. These include: * Multi-parameter typeclasses * Functional dependencies * Undecidable instances In all cases, these extensions are used to allow the typeclass abstractions to be expressed. These extensions are fairly popular and seem likely to make it in some form into a Haskell standard (hopefully in the not too distant future). Currently, Edison builds and runs correctly under GHC and Hugs. More specificly, most development and testing has been done with GHC 6.4.1, and the test suite builds and runs to completion with no errors. With Hugs (March 2005 release) and the '-98' option, all of the core Edison data structures should work correctly. Unfortunately, the test suite will not load, due to differences in Hugs' and GHC's implementations of multi-parameter typeclasses. As the extensions used are not recent developments, I also expect that less recent versions of GHC and Hugs will also work. Other implementations may also work correctly with Edison, but this has not been tested. The Story on Edison Packages ---------------------------------- Cabal is a nice tool for building and distributing Haskell projects. However, it has the slightly undesirable property that the "Package" unit is the atomic unit of compilation, documentation and of dependency resolution. In order to support implementations which have varying external dependencies, Edison has been split into multiple cabal sub-packages, which cooperate. The root package is named 'EdisonAPI' and it contains the typeclass specifications, together with extensive documentation and a few utility classes. 'EdisonAPI' essentially represents a design contract. The 'EdisonCore' package contains core Edison implementations. These implementations have no dependencies beyond the standard libraries. Other implementation modules are planned: these other modules may have dependencies on eg, Adiran Hay's AVL tree implementation or Don Stewart's Fast Packed String, etc. Additionally there is a unit test package. Currently it is tied to the 'EdisonCore' package, but in the future it will provide basic unit testing capabilities for extended implementations as well. Edison Versioning ----------------------- As the maintainer of Edison, I take API stability very seriously. My goal is that programs written against Edison will not suffer from version drift. However, I also wish to allow Edison to incorporate new ideas and evolve into a better way to use data structures in Haskell. In order to help accommodate these somewhat opposing goals, I have adopted the following versioning scheme. Respect the versioning scheme, and you should have no compatibility problems. Each Edison release number is composed of four components: xxx.yyy.zzz.www ^ ^ ^ ^ | | | | | | | +------ patch level | | +---------- API version number | +-------------- minor version number +------------------ major version number The API version number and/or patch level may be omitted for brevity. When omitted, they are assumed to be 0. I have adopted the (pre-2.6) Linux kernel versioning scheme for major and minor numbers: the major number is incremented at major updates (ie, something on the order of total API re-engineering or complete rewrites). Minor numbers represent "branches" of development. Releases with even minor numbers are "stable" releases (0 is considered even). For example, the Edison 1.2 release is a stable release. Even numbered releases will have stable user-visible APIs; my goal is that any program compiled against an Edison stable release will work correctly for all later Edison releases with the same major and minor version numbers. This means that API changes will be limited to additions. However, I intend that even additions be rare, and they will only be considered with compelling evidence that the lack of the feature in question inhibits desirable use cases. The user-visible behavior of an implementation will only be changed if it was originally in violation of the contract (ie, a bug). *NOTE* THE EXACT BEHAVIOR OF AMBIGUOUS OPERATIONS IS NOT CONSIDERED USER-VISIBLE BEHAVIOR, nor is the behavior of unsafe operations when used in violation of their preconditions. Ambiguous operations may change their behavior in stable releases as long as such changes still obey the design contract. Releases with odd minor numbers are "development" branches. Such releases are branched from the immediately preceding stable release minor number. For example, the Edison 1.3 development branch will be forked from the Edison 1.2 release family. No guarantees are made about the user-visible APIs for development branches. API operations may be added, deleted, or have the terms of their design contracts altered in development branches, and implementations may freely change their behavior. Eventually development branches are stabilized and transform into the next even-numbered stable release. For both even and odd minor numbers, the third component represents the "API version". Any change to the API will cause a bump in the API version number. For stable branches, this should be fairly rare; for odd branches, it may occur rather frequently. The fourth component is incremented for each official release whenever the first three components are not altered. Two Edison versions which differ only in their patch level should have identical APIs.