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
andnull
. Deriving these instead of using the defaults can change the orders of growth! Givendata Tree a = Bin !(Tree a) a !(Tree a) | Tip
, we surely don't wantnull
to traverse the whole spine of the tree when it's quite immediately obvious thatBin
is never null. And if a constructor contains a type with a very efficientlength
ornull
implementation (e.g., one that stores its own size), we certainly want to use that. -
foldl
typically ends up with rather different code thanfoldr
(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'
andfoldr'
are a bit tricky. Ideally, if we have something likedata T a = C (G a) a | ...
then we'd like to be able to useG
'sfoldl'
definition to defineT
's. Unfortunately, different types in the wild have differentfoldl'
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
Trac field | Value |
---|---|
Version | 8.0.1 |
Type | Task |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | Compiler |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | |
Architecture |