As others have said, it's not that ByteString
is fast, it's that String
is very, very slow.
A ByteString
stores one byte per character, plus some book-keeping overhead. A String
stores something like 12 bytes per character (depending on whether you're running in 32-bit or 64-bit mode). It also stores each character in non-contiguous memory, so each character has to have space individually allocated to it, individually scanned by the garbage collector, and eventually individually deallocated again. This means poor cache locality, lots of allocator time, and lots of garbage collection time. In short, it's hellishly inefficient.
Basically, ByteString
does what C does, what Java does, what C++ does, what C# does, what VB does, and what just about every other programming language does with strings. No other language I'm aware of has a default string type as inefficient as Haskell does. (Even Frege, which is a Haskell dialect, uses a more efficient string type.)
I should point out that ByteString.Char8
only handles Latin-1 characters. It doesn't cope with random Unicode characters at all. That probably isn't a problem for a programming challenge like this, but for a "real system" it might well be. ByteString
doesn't really deal with exotic characters or different character encodings or anything; it just assumes you want plain ASCII. That used to be a safe assumption; today, not so much.