Why is Haskell [] (list) not a type class?

Question

I am writing a Haskell function which takes a list as input. That is, there's no reason it couldn't be a queue or dequeue, or anything that allows me to access its "head" and its "tail" (and check if it's empty). So the [a] input type seems too specific. But AFAIK there's no standard library typeclass that captures exactly this interface. Sure, I could wrap my function in a Data.Foldable.toList and make it polymorphic wrt Foldable, but that doesn't quite seem right (idiomatic).

Why is there no standard list type class? (And why is the "container" type class hierarchy in Haskell less developed than I think it should be?) Or am I missing something essential?

Answer 1

A given algebraic datatype can be represented as its catamorphism, a transformation known as Church encoding. That means lists are isomorphic to their foldr:

type List a = forall b. (a -> b -> b) -> b -> b

fromList :: [a] -> List a
fromList xs = \f z -> foldr f z xs

toList :: List a -> [a]
toList l = l (:) []

But foldr also characterises Foldable. You can define foldMap in terms of foldr, and vice versa.

foldMap f = foldr (mappend . f) mempty
foldr f z t = appEndo (foldMap (Endo . f) t) z

(It shouldn't be surprising that foldMap :: Monoid m => (a -> m) -> [a] -> m characterises lists, because lists are a free monoid.) In other words, Foldable basically gives you toList as a class. Instances of Foldable have a "path" through them which can be walked to give you a list; Foldable types have at least as much structure as lists.

---

Regarding your misgivings:

It's not like Foldable has functions head/tail/isEmpty, which is what I would find more intuitive.

null :: Foldable t => t a -> Bool is your isEmpty, and you can define (a safe version of) head straightforwardly with an appropriate choice of Monoid:

head :: Foldable t :: t a -> Maybe a
head = getFirst . foldMap (First . Just)

tail is kinda tricky in my opinion. It's not obvious what tail would even mean for an arbitrary type. You can certainly write tail :: Foldable t => t a -> Maybe [a] (by toListing and then unconsing), but I think any type T for which tail :: T a -> Maybe (T a) is defined would necessarily be structurally similar to lists (eg Seq). Besides, in my experience, the vast majority of cases where you'd think you need access to a list's tail turn out to be folds after all.

That said, abstracting over unconsable types is occasionally useful. megaparsec, for example, defines a Stream class for (monomorphic) streams of tokens to be used as input for a parser.

Answer 2

The Question

Making your question more concrete, let's ask:

Why isn't the type class

class HasHeadAndTail t where
    head :: t a -> Maybe a
    tail :: t a -> Maybe (t a)
    isEmpty :: t a -> Bool

in the base library?

An Answer

This class is only useful for ordered, linear containers. Map, Set, HashMap, HashTable, and Tree all would not be instances. I'd even argue against making Seq and DList an instance since there are really two possible "heads" of that structure.

Also what can we say about any type that is an instance of this class? I think the only property is if isEmpty is False then head and tail should be non-Nothing. As a result, isEmpty shouldn't even be in the class and instead be a function isEmpty :: HashHeadAndTail t => t a -> Bool ; isEmpty = isNothing . head.

So my answer is:

• This class lacks utility in so far as it lacks instances.
• This class lacks useful properties and classes that lack properties are frequently discouraged.