[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 don't think that I have enough information to resolve this, but I've
 noticed some things that may help clarify the situation, for any onlookers
 or future developers who haven't already figured them out. Apologies if
 any of this is too obvious.

 1) The `wrap`, `unwrap`, `cons`, and `nil` definitions have to be examined
 in combination to check correctness. All are, in effect, defined by the
 consumer.

 I think that it's a bit confusing to have a `Wrap` type that only contains
 `wrap`/`unwrap` when (aside from the trivial `wrap . unwrap = id` case)
 the four have to be examined together to be understood. I'm agnostic as to
 whether that should be addressed by replacing `Wrap` with a new type that
 contains all four, or if `wrap`/`unwrap` pairs are so closely linked that
 it justifies pairing them separately. Aside from `isoSimple`, I'm not sure
 if many `Wrap` definitions would be reusable for very many consumers.

 2) Producers are relatively constrained due to the use of `forall` in
 `buildW` and `Wrap`. Since consumers choose the definition of
 `wrap`/`unwrap`/`cons`/`nil` they are much freer. In an ideal (but
 unproven) case, all producers using buildW would be good, given sufficient
 constraints on of consumers.

 3) These rules seem to me to be ''sufficient'' to ensure that a consumer
 is correct (disregarding the treatment of _|_):
 {{{
 wrap . unwrap $ cons = cons
 wrap . unwrap $ (\ _ _ -> nil) = \ _ _ -> nil
 }}}
 I've started to sketch a proof of this, but to be frank I'm rather new to
 this sort of analysis and not at all confident. I'd be perfectly happy
 either to discuss this, or for someone else to beat me there, or give a
 counterexample. (I'm also not sure that `unwrap . wrap = id` is important,
 though probably pairs with this property are easier to understand.)

 4) I have much less confidence that my conditions in (3) are necessary
 than that they are sufficient. They hold for `isoSimple` and the `foldl`
 implementation by Takano Akio, but I have not quite wrapped my head
 around, for instance, the scanl implementation here:

 https://github.com/dolio/ww-fusion

 This seems to get to the vague neighborhood of the condition on cons in
 (3), but not quite there, which suggests that either that condition needs
 to be expanded, or else that this implementation fails for some use of
 scanl that I haven't tested.

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