# Difference between revisions of "Applications and libraries/Data structures"

From HaskellWiki

DonStewart (talk | contribs) (+Streams and Arrays&Ref lib) |
(added AltBinary and more info about Streams and ArrayRef) |
||

Line 15: | Line 15: | ||

;[http://www.cs.vu.nl/Strafunski/ Strafunski] |
;[http://www.cs.vu.nl/Strafunski/ Strafunski] |
||

:A bundle for generic programming. It provides programming support for generic traversal as useful in the implementation of program transformations. |
:A bundle for generic programming. It provides programming support for generic traversal as useful in the implementation of program transformations. |
||

− | |||

⚫ | |||

⚫ | :This is a short preprocessor for stateful Haskell programs. It aleviates the pain of performing single array lookup/write/update functions with some syntax to support it. It also supports hash table operations based on the HashTable implementation available from the author. Finally, it supports monadic if and monadic case constructions. It is lightweight in the sense that it performs no syntactic analysis and is essentially a character transformer. |
||

;[http://www.lochan.org/2005/keith-cl/libs/ Partial v0.1] |
;[http://www.lochan.org/2005/keith-cl/libs/ Partial v0.1] |
||

Line 30: | Line 27: | ||

;[http://www.cwi.nl/~ralf/HList/ HList] |
;[http://www.cwi.nl/~ralf/HList/ HList] |
||

:A heterogeneous collection is a datatype that is capable of storing data of different types, while providing operations for look-up, update, iteration, and others. There are various kinds of heterogeneous collections, differing in representation, invariants, and access operations. |
:A heterogeneous collection is a datatype that is capable of storing data of different types, while providing operations for look-up, update, iteration, and others. There are various kinds of heterogeneous collections, differing in representation, invariants, and access operations. |
||

− | |||

− | ;[http://article.gmane.org/gmane.comp.lang.haskell.cafe/11230 Fast mutable variables for IO and ST] |
||

− | :Bulat Ziganshin's preliminary code for fast mutable variables in IO and ST. |
||

;[http://www.csee.ogi.edu/~diatchki/monadLib monadLib] |
;[http://www.csee.ogi.edu/~diatchki/monadLib monadLib] |
||

Line 65: | Line 59: | ||

=== IO === |
=== IO === |
||

− | ;[http:// |
+ | ;[http://haskell.org/haskellwiki/Library/Streams Streams] |

− | : |
+ | :Streams is a feature-rich, flexible, extensible, backward-compatible and fast |

+ | I/O library. It supports various stream types: plain and memory-mapped |
||

+ | files, string and memory buffers, pipes. There is also |
||

+ | common functionality, available for any stream: buffering, Char |
||

+ | encoding, locking. |
||

+ | |||

=== Mutable data === |
=== Mutable data === |
||

⚫ | |||

⚫ | |||

⚫ | :This is a short preprocessor for stateful Haskell programs. It aleviates the pain of performing single array lookup/write/update functions with some syntax to support it. It also supports hash table operations based on the HashTable implementation available from the author. Finally, it supports monadic if and monadic case constructions. It is lightweight in the sense that it performs no syntactic analysis and is essentially a character transformer. |
||

+ | |||

⚫ | |||

:Featuring: |
:Featuring: |
||

− | * Unboxed references in IO and ST |
+ | * Unboxed references in IO and ST monads |

* Monad-independent interfaces to boxed and unboxed references |
* Monad-independent interfaces to boxed and unboxed references |
||

* Syntax sugar to make using of mutable objects easier (=:, +=, -=,..) |
* Syntax sugar to make using of mutable objects easier (=:, +=, -=,..) |
||

− | and more. |
||

+ | * Reimplemented Arrays library with the following improvements: |
||

+ | ** Unboxed arrays now can be used in polymorphic functions |
||

+ | ** The MArray class now supports arrays with dynamic bounds |
||

+ | ** Implementation of dynamic (resizable) arrays |
||

=== Strings === |
=== Strings === |
||

Line 93: | Line 93: | ||

=== Serialising data === |
=== Serialising data === |
||

− | ;[http://www.n-heptane.com/nhlab/repos/NewBinary |
+ | ;[http://www.n-heptane.com/nhlab/repos/NewBinary NewBinary] |

− | :A port of Malcolm Wallace's Binary library from NHC, offering facilities for heap compression and binary I/O. The de-facto standard for binary |
+ | :A port of Malcolm Wallace's Binary library from NHC, offering facilities for heap compression and binary I/O. The de-facto standard for binary I/O in Haskell |

;[http://www.cs.helsinki.fi/u/ekarttun/SerTH/ SerTH] |
;[http://www.cs.helsinki.fi/u/ekarttun/SerTH/ SerTH] |
||

:SerTH is a binary serialization library for Haskell. It supports serializing cyclic datatypes in a fast binary format. SerTH uses template haskell for deriving the serializing interface for new datatypes. |
:SerTH is a binary serialization library for Haskell. It supports serializing cyclic datatypes in a fast binary format. SerTH uses template haskell for deriving the serializing interface for new datatypes. |
||

− | ;[http://freearc.narod.ru ByteStream] |
||

+ | ;[http://haskell.org/haskellwiki/Library/AltBinary AltBinary] |
||

− | :ByteStream is like the NHC Binary library. It provides marshalling of Haskell objects to byte streams and restoring them back. |
||

+ | : AltBinary is an exhaustive library that support binary I/O and serialization. It's part of [http://haskell.org/haskellwiki/Library/Streams Streams] library, so serialization is possible to any I/O source, from String to memory-mapped file. It's also backward compatible with [http://www.n-heptane.com/nhlab/repos/NewBinary NewBinary] library what makes translation of old code trivial. Very fast, very feature-rich, Hugs/GHC compatible, etc, etc... |
||

=== Compressing data === |
=== Compressing data === |
||

Line 106: | Line 106: | ||

;[http://freearc.narod.ru/ Compression-2005] |
;[http://freearc.narod.ru/ Compression-2005] |
||

:Features of the Compression-2005 Library: |
:Features of the Compression-2005 Library: |
||

− | * easy and uniform access to most competitive compression algorithms as of April |
+ | * easy and uniform access to most competitive free compression algorithms as of April'05: LZMA, PPMd and GRZip |

* all input/output performed via user-supplied functions (callbacks), so you can compress data in memory, files, pipes, sockets and anything else |
* all input/output performed via user-supplied functions (callbacks), so you can compress data in memory, files, pipes, sockets and anything else |
||

* all parameters of compression algorithm are defined with a single string, for example "lzma:8mb:fast:hc4:fb32". |
* all parameters of compression algorithm are defined with a single string, for example "lzma:8mb:fast:hc4:fb32". |
||

+ | Using this library, you can write whole bzip-like utility as one-liner! And it will compress even better than bzip2! |
||

=== Benchmarking data structures === |
=== Benchmarking data structures === |

## Revision as of 15:57, 18 August 2006

*The copyright status of this work is not known. Please help resolve this on the talk page.*

*This page contains a list of libraries and tools in a certain category. For a comprehensive list of such pages, see Applications and libraries.*

## Contents

## Haskell Libraries and Tools for Data Structures

- Edison
- This is the latest version of the Edison library of efficient data structures. There are also earlier version of Edison by Chris Okasaki. It provides sequences, finite maps, priority queues, and sets/bags. (overview paper).

- Data.Tree.AVL
- An implementation of AVL trees and related utilities.

- Data.StringMap
- A library providing maps from String keys to values, based on Tries.

- Strafunski
- A bundle for generic programming. It provides programming support for generic traversal as useful in the implementation of program transformations.

- Partial v0.1
- The Partial library provides a partial order class. It also provides routines for generating a Hasse diagram from a set and a partial order. Renderers are provided for the abstract Hasse diagram representation into LaTeX (via Xy-pic) and into dot, the format for AT&T's Graphviz tools. Since no horizontal sorting is done, the Xy-pic output is rather poor at present; dot does a much better job with its layout optimisation algorithm.

- Discrete Interval Encoding Trees
- The discrete interval encoding tree is a structure for storing subsets of types having a total order and a predecessor and a successor function.

- Ranged Sets
- A ranged set is a list of non-overlapping ranges. The ranges have upper and lower boundaries, and a boundary divides the base type into values above and below. No value can ever sit on a boundary. So you can have the set {2.0 < x <= 3.0, 5.3 < x < 6}

- HList
- A heterogeneous collection is a datatype that is capable of storing data of different types, while providing operations for look-up, update, iteration, and others. There are various kinds of heterogeneous collections, differing in representation, invariants, and access operations.

- monadLib
- Iavor Diatchki's library of monad transformers for Haskell. It enables the quick construction of monads --- abstract data types that capture common programming idioms, such as throwing and catching exceptions or continuations. In many programming languages such features are built into the language (if they're provided at all), but in Haskell they are user-programmable.

- Pointless Haskell
- Pointless Haskell is library for point-free programming with recursion patterns defined as hylomorphisms. It also allows the visualization of the intermediate data structure of the hylomorphisms with GHood. This feature together with the DrHylo tool allows us to easily visualize recursion trees of Haskell functions.

- rhaskell : Reactive Objects
- Stefan Wehr's reactive objects library. Reactive objects are a convenient abstraction for writing programs which have to interact with a concurrent environment. A reactive object has two characteristics: the abandonment of all blocking operations and the unification of the concepts state and process. The former allows a reactive object to accept input from multiple sources without imposing any ordering on the input events. The latter prevents race conditions because the state of an object is only manipulated from the process belonging to the object.

- GenUtil
- A collection of random useful utility functions written in pure Haskell 98. In general, it trys to conform to the naming scheme put forth the Haskell prelude and fill in the obvious omissions, as well as provide useful routines in general.

- PersistentDocument
*The link is dead, somebody please either update it or remove it.* - The persistent document abstraction takes care of dealing with a document you want to open from and save to disk and that supports undo. This functionality can be used by editors of arbitrary documents and saves you a lot of quite subtle coding.

- Zipper monad
- A generic monad for navigating around arbitrary data structures

### Graphs

- FGL - A Functional Graph Library
- The functional graph library provides a collection of graph operations.

- Data.Relation
- Part of the UMinho Haskell libraries, this library provides a representation and operations on relations. A special case of relations are graphs. The operations include graph chopping and slicing, strong connected component analysis, graphs metrics, and more.

- Haskell Graph Automorphism Library
- Jean-Philippe Bernardy's implementation of Brendan McKay's algorithm for graph canonic labeling and automorphism group (Nauty).

### IO

- Streams
- Streams is a feature-rich, flexible, extensible, backward-compatible and fast

I/O library. It supports various stream types: plain and memory-mapped files, string and memory buffers, pipes. There is also common functionality, available for any stream: buffering, Char encoding, locking.

### Mutable data

- The Haskell STate Preprocessor
- This is a short preprocessor for stateful Haskell programs. It aleviates the pain of performing single array lookup/write/update functions with some syntax to support it. It also supports hash table operations based on the HashTable implementation available from the author. Finally, it supports monadic if and monadic case constructions. It is lightweight in the sense that it performs no syntactic analysis and is essentially a character transformer.

- Arrays & References Library
- Featuring:

- Unboxed references in IO and ST monads
- Monad-independent interfaces to boxed and unboxed references
- Syntax sugar to make using of mutable objects easier (=:, +=, -=,..)
- Reimplemented Arrays library with the following improvements:
- Unboxed arrays now can be used in polymorphic functions
- The MArray class now supports arrays with dynamic bounds
- Implementation of dynamic (resizable) arrays

### Strings

- Data.ByteString
- The FPS library provides mmapped and malloc'd packed strings (byte arrays held by a ForeignPtr), along with a list interface to these strings. It lets you do extremely fast IO in Haskell; in some cases, even faster than typical C implementations, as well as conserving space.

- MissingH
- MissingH is a library of pure-Haskell utility functions relating to strings, logging, and I/O.

- HsLocale
- A locale-aware replacement for the standard IO routines, and support for
*wide*strings

- VariableExpansion
- A library for variable expansion inside strings

### Serialising data

- NewBinary
- A port of Malcolm Wallace's Binary library from NHC, offering facilities for heap compression and binary I/O. The de-facto standard for binary I/O in Haskell

- SerTH
- SerTH is a binary serialization library for Haskell. It supports serializing cyclic datatypes in a fast binary format. SerTH uses template haskell for deriving the serializing interface for new datatypes.

- AltBinary
- AltBinary is an exhaustive library that support binary I/O and serialization. It's part of Streams library, so serialization is possible to any I/O source, from String to memory-mapped file. It's also backward compatible with NewBinary library what makes translation of old code trivial. Very fast, very feature-rich, Hugs/GHC compatible, etc, etc...

### Compressing data

- Compression-2005
- Features of the Compression-2005 Library:

- easy and uniform access to most competitive free compression algorithms as of April'05: LZMA, PPMd and GRZip
- all input/output performed via user-supplied functions (callbacks), so you can compress data in memory, files, pipes, sockets and anything else
- all parameters of compression algorithm are defined with a single string, for example "lzma:8mb:fast:hc4:fb32".

Using this library, you can write whole bzip-like utility as one-liner! And it will compress even better than bzip2!

### Benchmarking data structures

- Auburn
- Auburn is Graeme Moss's kit for benchmarking implementations of lazy data structures. Give it several implementations of an ADT (abstract data type) and it will tell you which one is best for your particular application.

- Bench
- Simple time and space benchmarking for various list-like data structures. Easily adapted to arbitrary structures