#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.
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
Quite possibly. 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.
4) I have much less confidence that my conditions in (3) are necessary
What makes a producer valid is not so clear, but yes, it seems less complicated than the consumer side. 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:
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