Rewriting Haskell Strings

This paper caught my eye, and it turned out to be really great. Unlike what the abstract might suggest their approach actually generalizes to any data type that can be faithfully converted to and from streams.

Rewriting Haskell Strings
by Duncan Coutts, Don Stewart, and Roman Leshchinskiy

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 expressiveness and performance over previous functional
array fusion strategies. A library for ByteStrings is implemented, providing
a purely functional interface, which approaches the speed of low-level
mutable arrays in C.

Available from