Rewriting Haskell Strings
In PADL'07: 9th International Symposium on Practical Aspects of
Declarative Languages, pp. 50-64, Springer-Verlag, 2007
Received the Most Practical Paper Award at PADL 2007
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.
See Don's ByteString page.