[Haskell] string type class

Chris Kuklewicz haskell at list.mightyreason.com
Fri Mar 6 14:16:33 EST 2009

Matthew Pocock wrote:
> It seems every time I look at hackage there is yet another stringy 
> datatype. For lots of apps, the particular stringy datatype you use 
> matters for performance but not algorithmic reasons. Perhaps this is a 
> good time for someone to propose a stringy class?

Not likely.

I did define my own (private) class for regular expressions, to abstract over 
String, the ByteStrings, and Seq Char.  But it is used in one place and is a 
wart that should be removed.

The simple task of looping over the contents of a String (once, forward) is 
quite different from a Strict ByteString (using an index and a lookup).

This means for decent efficiency I need two copies of my code, hand specialized 
to each case.

"tail" or "(x:xs)" : very efficient for String (no allocation)
"tail" or "uncons" : not efficient for ByteString (allocation, might as well 
convert to [Char]

And indexing by Int is O(n) for String and O(1) for ByteString.

So there are few algorithm that can access both efficiently.

More information about the Haskell mailing list