[Haskell-cafe] The Proliferation of List-Like Types

[John Goerzen]

Hi folks,

Before I started using Haskell, I used OCaml for a spell.  One of my
biggest annoyances with OCaml was that it had two list types: the
default list (strict), and a lazy list (known as a stream).

This led to all sorts of annoyances.  Libraries were always written to
work with one list or the other.  If you wanted to use two libraries,
one that assumed one list and the other that assumed another, you had
a difficult task ahead of you.

I am concerned that the same thing is happening in Haskell.  We know
have three common list-like types: the regular list, strict
ByteString, and lazy ByteString.

This has created some annoying situations.  For instance, a ByteString
is great for reading data fast, but Parsec doesn't work on
ByteStrings.  I am glad that someone wrote a Parsec equivolent that
does[1], which answers a real need.  But this means that all the
combinators in the hsemail library that implement standard RFC
conventions won't be usable in my ByteString code, for instance.

Similarly, we have another annoying situation relating to character
encodings:

 * The iconv library works only on lazy ByteStrings, and does not
   handle Strings or strict ByteStrings

 * The utf8-string library doesn't support UTF-16, doesn't require an
   external library, and works only on Strings -- no support for
   ByteStrings.

 * Data.Encoding.* is native haskell, supports UTF-*, but works only
   on ByteSting.Lazy again.

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)

These instances use the native underlying calls where appropriate (for
instance, ByteString and Data.List both provide a 'head').  The
typeclass also contains large numbers of default implementations, such
that only four functions must be implemented to make a type a member
of ListLike.  API ref is at 

  http://software.complete.org/listlike/static/doc/ListLike/Data-ListLike.html#intro

Now, the questions:

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

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

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].

[1] Yes, I have read about Parsec 3 being imminent, which is also great

[2] http://software.complete.org/listlike