Consider deriving more Foldable methods
We currently derive
foldr, but some others may deserve attention as well.
- The most critical spots are probably
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
nullto traverse the whole spine of the tree when it's quite immediately obvious that
Binis never null. And if a constructor contains a type with a very efficient
nullimplementation (e.g., one that stores its own size), we certainly want to use that.
foldltypically 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.
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
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.