#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