Now, to help solve this problem, I wrote ListLike[2], providing a set of typeclasses that make list operations generic. I also provided default instances of ListLike for:

ListLike Data.ByteString.ByteString Word8 ListLike Data.ByteString.Lazy.ByteString Word8 ListLike [a] a (Integral i, Ix i) => ListLike (Array i e) e (Ord key, Eq val) => ListLike (Map key val) (key, val)

It's a multi-parameter type class, right? So it's difficult to push it to the core.

Now, the questions:

1) Does everyone agree with me that we have a problem here?

I agree.

2) Would it make sense to make ListLike, or something like it, part of the Haskell core?

Somehow yes. However since the 'base' package is constantly split into smaller parts, there is maybe no need to merge it somewhere, but introduce simply new package dependencies.

3) Would it make sense to base as much code as possible in the Haskell core areound ListLike definitions? Here I think of functions such as lines and words, which make sense both on [Char] as well as ByteStrings.

4) We are missing one final useful type: a Word32-based ByteString. When working in the Unicode character set, a 32-bit character can indeed be useful, and I could see situations in which the performance benefit of a ByteString-like implementation could be useful combared to [Char].

StorableVector should fill this gap. http://code.haskell.org/~sjanssen/storablevector/