[GHC] #9545: Evaluate Takano Akio's foldrW/buildW fusion framework as a possible replacement for foldr/build

[GHC]

#9545: Evaluate Takano Akio's foldrW/buildW fusion framework as a possible
replacement for foldr/build
-------------------------------------+-------------------------------------
              Reporter:  dfeuer      |            Owner:
                  Type:  task        |           Status:  closed
              Priority:  normal      |        Milestone:
             Component:              |          Version:  7.9
  libraries/base                     |         Keywords:
            Resolution:  wontfix     |     Architecture:  Unknown/Multiple
      Operating System:              |       Difficulty:  Project (more
  Unknown/Multiple                   |  than a week)
       Type of failure:              |       Blocked By:
  None/Unknown                       |  Related Tickets:
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------

Comment (by quantheory):

 I have done a little bit more on this, so can elaborate.

 > Unclear. `wrap . unwrap = id` seems to strong—I don't ''think'' any non-
 trivial wrappers satisfy it.

 I agree. From what I've seen so far, `wrap . unwrap = id` only fits in
 cases where `build`/`foldr` already worked in the first place.


 > What makes a producer valid is not so clear, but yes, it seems less
 complicated than the consumer side.
 > [...]
 > This implementation fails for some reason you haven't tested.

 My hope had been that if the definition of a good consumer could be nailed
 down well enough, then producers would be trivial. But it's looking
 increasingly difficult to get this right.

 I did find the issues with scanl and reverse; in fact, even after fixing
 `reverse . scanl f z $ xs`, I still had issues with `reverse . scanl f z .
 reverse $ xs`. But I did eventually fix both cases with this change:

 https://github.com/quantheory/ww-
 fusion/commit/74618328c34572270154dbd93eb441f448760e0e

 It seems that, on top of needing `wrap . unwrap $ cons = cons`, if you
 have multiple layers of wrapper, there are more conditions needed to
 ensure that one wrapper doesn't break an invariant relied upon by an
 underlying wrapper.

 My first attempted fix for scanl used `k` twice, attempting to throw away
 the result in one case. But it turned out that, when combined with
 `reverse`, the extra `k b` would be moved to where it could insert extra,
 wrong values into the stream. This is why, in the commit linked above, I
 use `n` in `scanlWrap`: presumably `n` should never add new values.

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