In Haskell, why isn’t there a TypeClass for things that can act like lists?

by

The ListLike package seems to provide what you’re looking for. I’ve never understood why it isn’t more popular.

ListLike aside, one reason this isn’t implemented in the Prelude is because it’s not possible to do so well without invoking some language extensions (multi-param type classes and fundeps or associated types). There are three sorts of containers to consider:

  1. Containers that don’t care about their elements at all (e.g. [])
  2. Containers which are only implemented for specific elements (e.g. bytestrings)
  3. Containers which are polymorphic over elements but require a context
    (e.g. Data.Vector.Storable, which will
    hold any type with a storable
    instance).

Here’s a very basic ListLike-style class without using any extensions:

class Listable container where
  head :: container a -> a

instance Listable [] where
  head (x:xs) = x

instance Listable ByteString where --compiler error, wrong kind

instance Listable SV.Vector where
  head v = SV.head    --compiler error, can't deduce context (Storable a)

Here container has kind *->*. This won’t work for bytestrings because they don’t allow an arbitrary type; they have kind *. It also won’t work for a Data.Vector.Storable vector, because the class doesn’t include the context (the Storable constraint).

You can fix this problem by either changing your class definition to

class ListableMPTC container elem | container -> elem where

or

class ListableAT container where
  type Elem container :: *

Now container has kind *; it’s a fully-applied type constructor. That is, your instances look like

instance ListableMPTC [a] a where

but you’re no longer Haskell98.

That’s why even a simple Listable-type interface is non-trivial; it gets a bit harder when you have different collection semantics to account for (e.g. queues). The other really big challenge is mutable-vs.-immutable data. So far every attempt I’ve seen (except one) punts on that issue by creating a mutable interface and an immutable one. The one interface I know which did unify the two was mind-bending, invoked a bunch of extensions, and had quite poor performance.

Addendum: bytestrings

Totally conjecture on my part, but I think we’re stuck with bytestrings as a product of evolution. That is, they were the first solution to low performance I/O operations, and it made sense to use Ptr Word8s for interfacing with IO system calls. Operations on pointers require Storable, and most likely the necessary extensions (as described above) to make polymorphism work weren’t available then. Now it’s difficult to overcome their momentum. A similar container with polymorphism is certainly possible, the storablevector package implements this, but it’s not anywhere near as popular.

Could bytestrings be polymorphic without any restrictions on the elements? I think the closest Haskell has to this is the Array type. This isn’t nearly as good as a bytestring for low-level IO because data needs to be unpacked from the pointer into the array’s internal format. Also the data is boxed, which adds significant space overhead. If you want unboxed storage (less space) and efficient interfacing with C, pointers are the way to go. Once you have a Ptr, you need Storable, and then you need to include the element type in the type class, so then you’re left with requiring extensions.

That being said, I think that with the appropriate extensions available this is essentially a solved problem for any single container implementation (modulo mutable/immutable APIs). The harder part now is coming up with a sensible set of classes that are usable for many different types of structures (lists, arrays, queues, etc.) and is flexible enough to be useful. I personally would expect this to be relatively straightforward, but I could be wrong.

Leave a Comment