Search code examples
haskellchurch-encodingdifference-lists

Why are difference lists not an instance of foldable?


The dlist package contains the DList data type, which has lots of instances, but not Foldable or Traversable. In my mind, these are two of the most "list-like" type classes. Is there a performance reason that DList is not an instance of these classes?

Also, the package does implement foldr and unfoldr, but none of the other folding functions.


Solution

  • DList a is a newtype wrapper around [a] -> [a], which has an a in a contravariant position, so it cannot implement Foldable or Traversable, or even Functor directly. The only way to implement them is to convert to and from regular lists (see the foldr implementation), which defeats the performance advantage of difference lists.