Consider deriving more Foldable methods

We currently derive foldMap and foldr, but some others may deserve attention as well.

The most critical spots are probably length and null. Deriving these instead of using the defaults can change the orders of growth! Given data Tree a = Bin !(Tree a) a !(Tree a) | Tip, we surely don't want null to traverse the whole spine of the tree when it's quite immediately obvious that Bin is never null. And if a constructor contains a type with a very efficient length or null implementation (e.g., one that stores its own size), we certainly want to use that.
foldl typically ends up with rather different code than foldr (for a recursive type) even after simplification. We need to check whether this has a performance impact, but my bet is that it will in cases where the optimizer can't understand what's going on well enough.
foldl' and foldr' are a bit tricky. Ideally, if we have something like data T a = C (G a) a | ... then we'd like to be able to use G's foldl' definition to define T's. Unfortunately, different types in the wild have different foldl' semantics (and indeed the semantics for [] changed by mistake fairly recently). So we have to decide to what extent the derived semantics should depend on the choices of included types. I think we should probably just depend, because that seems likely what people will expect and want.

Trac metadata

To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information