GHC 8.4 DeriveFoldable will derive the definition of `null` rather
than falling back on the default. This can produce dramatic
performance improvements. I would like to do the same for `length`,
but unfortunately, there's a problem.
### Why I want to derive length
Consider the declaration
data Foo a = Foo (Map "String" a) (Set a)
A hand-written definition of `length` would look like this:
length (Foo m set) = length m + length set
This would produce an O(1) implementation of length, since Map and Set
are annotated with their lengths. But the default implementation of
length (which is what you get when you use `deriving Foldable`) would
length foo = foldl' (\acc _ -> acc + 1) 0 foo
which is O(n). Gross.
### What's the problem?
There's no problem deriving length for Foo. The trouble comes when
trying to derive length for a recursive type.
data List a = Nil | Cons a (List a)
The most obvious implementation to derive would be
length Nil = 0
length (Cons _ xs) = 1 + length xs
but this is not tail recursive! That's absolutely no good. What we
*want* here is