[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 dfeuer):

 Replying to [comment:5 quantheory]:
 > 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.

 Quite possibly.

 > 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.

 Unclear. `wrap . unwrap = id` seems to strong—I don't ''think'' any non-
 trivial wrappers satisfy it. Joachim thinks there could be a way to use
 parametricity to come up with a better criterion, and he may very well be
 right, but whether even a weaker one would be sufficient to implement
 enough useful functions is unclear.

 > 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.

 What makes a producer valid is not so clear, but yes, it seems less
 complicated than the consumer side.

 > 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 implementation fails for some reason you haven't tested. There are
 very bad interactions between the "static" stuff and `reverse`, and
 between `scanl` and `reverse`, leading to incorrect results. I tend to
 blame the static stuff and the `scanl` wrapper, but we don't really know
 if they would work right in all circumstances without `reverse`. Your
 efforts to find "local" correctness criteria are appreciated. My sense is
 that the `scanl` wrapper and the static stuff are problematic because they
 throw away information that someone else needs. The static stuff is an
 optimization that may be obviated by work on the static argument
 transformation. Whether there is a valid wrapper for `scanl` is as yet
 unclear.

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