Deriving length better: missing method problem

[David Feuer]

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
instead produce

   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

  length = lengthPlus 0
  lengthPlus acc Nil = acc
  lengthPlus !acc (Cons _ xs) = lengthPlus (acc + 1) xs

We actually could arrange for that in this case, since we see that a
`List` contains itself recursively. But what about *mutual* recursion?

  data List2 a = Nil | Cons a (List2' a)
  newtype List2' a = List2' (List2 a)

Now the deriving mechanism can't see the recursion, and everything is horrible.

### The simplest solution

It seems likely that the simplest solution would be what nobody really
wants: add yet another method to Foldable:

  lengthPlus :: Int -> f a -> Int
  lengthPlus n xs = n + length xs

We could derive efficient implementations of `lengthPlus` without any
particular difficulty.

### Alternatives?

I haven't thought of any plausible alternatives yet. Maybe someone else will.

David