[GHC] #13280: Consider deriving more Foldable methods

[GHC]

#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