#13280: Consider deriving more Foldable methods -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: task | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: Runtime Unknown/Multiple | performance bug Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- 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. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13280 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler