Rewriting Haskell Strings

Duncan Coutts¹, Don Stewart² and Roman Leshchinskiy²

¹Programming Tools Group
Oxford University Computing Laboratory

²Computer Science & Engineering
University of New South Wales

Awarded "Most Practical Paper" at PADL 2007, Nice France.

Abstract

The Haskell String type is notoriously inefficient. We introduce a new data type, ByteString, based on lazy lists of byte arrays, combining the speed benefits of strict arrays with lazy evaluation. Equational transformations based on term rewriting are used to deforest intermediate ByteStrings automatically. We describe novel fusion combinators with improved expressivity and performance over previous functional array fusion strategies. A library for ByteStrings is implemented, providing a purely functional interface, and approaches the speed of low-level mutable arrays in C.

Full Text

The full text of the paper can be downloaded: (ps.gz ,pdf)

Source code

The source code for the Data.ByteString library, and examples used in the paper, can be downloaded:

darcs get --partial http://www.cse.unsw.edu.au/~dons/code/fps-unstable
Read the source code
The home of the Data.ByteString project

Applications

The following applications use Data.ByteString:

Pugs, an implementation of Perl 6, written in Haskell
HAppS, a Haskell library for building industrial strength Internet applications
Freespire, a Linux distribution, that uses Haskell for its package tools
lambdabot, an IRC bot and Haskell IDE.
binary, high performance binary serialisation in pure Haskell
Hope, an extensible Haskell content management system
Hogg, Ogg encapsulation in Haskell
Text.Regex.Lazy, a high-performance regex library for Haskell
Yi, an extensible text editor
hIDE, an extensible Haskell IDE
crypto, a Haskell crypto library
HaskellNet, a unified Haskell networking library
hmp3, a curses-based mp3 player
BitSyntax, Erlang-like bit syntax for Haskell
zlib, gzip bindings
bzlib, bzip bindings
network-alt, High-perf alternative networking library
fast-cgi, Haskell library for writing FastCGI programs
BioHaskell, bioinformatics libraries for Haskell
TimeLib, The Haskell "time" package
conjure, a Haskell Bittorrent client
h4sh, use Haskell List functions as normal unix shell commands
DirectConnect, A framework for interacting with DirectConnect Hubs and clients
downnova, automate the process of downloading TV series from mininova.org
darcs-graph, draw graphs of darcs repository activity
Haskell UM, Universal Machine implementations in Haskell

BibTeX Entry

@inproceedings{CSL06,
    author = {Duncan Coutts and Don Stewart and Roman Leshchinskiy},
    title  = {Rewriting Haskell Strings},
    booktitle = {Practical Aspects of Declarative Languages 8th International Symposium, PADL 2007},
    year   = 2007,
    month  = jan,
    pages  = {50--64},  
    publisher = {Springer-Verlag},
}

Mon Oct 23 11:56:34 EST 2006