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?

History, and also laziness makes it less necessary. For example, toList essentially gives you an iterator because it's a lazy list. — luqui
I think it's tricky to identify the "correct" interface that captures a wide enough notion of "what you can do with a list" that you can actually implement reasonable algorithms with it generically, while still allowing reasonable implementations that aren't structurally similar to the native []. Operating by consing and deconsing individual elements at the head is hugely inefficient for array-like structures, for example. That said, there are things like hackage.haskell.org/package/ListLike — Ben
Why does defining your function to take a Foldable t => t a argument seem wrong? — chepner
@chepner, there's nothing wrong about it, I guess, but it'd just be a wrapper that calls the original function with toList of the argument. It's not like Foldable has functions head/tail/isEmpty, which is what I would find more intuitive. — dainichi

Benjamin Hodgson Benjamin Hodgson · Accepted Answer · 2017-03-01T03:27:43

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.

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

2 Answers