[GHC] #7994: Make foldl into a good consumer

[GHC]

#7994: Make foldl into a good consumer
-------------------------------------+------------------------------------
        Reporter:  simonpj           |            Owner:
            Type:  bug               |           Status:  new
        Priority:  normal            |        Milestone:
       Component:  Compiler          |          Version:  7.6.3
      Resolution:                    |         Keywords:
Operating System:  Unknown/Multiple  |     Architecture:  Unknown/Multiple
 Type of failure:  None/Unknown      |       Difficulty:  Unknown
       Test Case:                    |       Blocked By:
        Blocking:                    |  Related Tickets:
-------------------------------------+------------------------------------

Comment (by nomeata):

 So, this is what we want to happen, somehow.

 We want to transform code of the form
 {{{
 let f = λ x. let h = f (g1 x)
              in λ y... h (g2 y) ...
 in ...f 1 2..... f 3 4 ...
 }}}
 into
 {{{
 let f = λ x y. let h = f (g1 x)
                in ... h (g2 y) ...
 in ...f 1 2..... f 3 4 ...
 }}}

 If `g1` is cheap, this is already done (see `[Arity analysis]` in
 `CoreArity`). But in order to implement `foldl` in terms of `foldr` and
 get list fusion for it (which would be nice), this needs to work also when
 `g1` is expensive.

 In a slightly more general setting, the transformation would not be ok,
 e.g. in
 {{{
 let f = λ x. let h = f (g1 x)
              in λ y... h (g2 y) ...
 in ...map (f 1)....
 }}}
 or
 {{{
 let f = λ x. let h = f (g1 x)
              in λ y... map h...
 in ...f 1 2..... f 3 4 ...
 }}}
 because the expensive `g1` would no longer be shared.

 So we want an analysis that
  * looks at the call-sites of `f`
  * notices that the demand put on `f` from the body of the let,
 `C(C¹(S))`, is actually better than the vanilla demand `C(S)`,
  * makes sure that with this demand put on `f`, its definition (the rhs)
 now also has this demand (i.e. no sharing lost in the right hand sid),
  * uses this to mark the `λ y` as one-shot, which will presumably allow
 the desired optimization.

 The demand analyser currently analyses the function before the body. One
 could do a second round, but there is a risk of exponential blow-up.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/7994#comment:3>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler