#4342: Review containers changes
----------------------------------+-----------------------------------------
Reporter: igloo | Owner:
Type: bug | Status: new
Priority: high | Milestone: 7.2.1
Component: libraries (other) | Version: 7.1
Keywords: | Testcase:
Blockedby: | Difficulty:
Os: Unknown/Multiple | Blocking:
Architecture: Unknown/Multiple | Failure: None/Unknown
----------------------------------+-----------------------------------------
Comment(by milan):
Hi,
the new version of the patch is attached. There were only trivial renames
to silence the warnings (defined but not used variables and name
shadowings) and comments to the source code explaining the subtleties.
The new version is attached here and also present in the mentioned
repository http://fox.auryn.cz/darcs/containers/.
Looking at the igloo's mail with issues, these are still unresolved:
> There are some things I'll leave to the containers experts to review:
> I haven't checked the balance/balanceL/balanceR changes at all (neither
the definitions, nor the calls).
> I haven't checked the <= to < change in join and merge.
These two points are connected -- the rebalance was not done in accordance
with the original paper, but a bit sooner. Now it is rebalanced after the
balance is lost, not when it is just on the boundary.
Other than that, balance is just trivial inlines of rotateL && others. The
original definition is kept in the source for reference. The balanceL and
balanceR are just parts of balance, where the balance condition can be
broken only in one subtree.
> I haven't checked the change of delta from 4 to 3.
I have a proof that it is correct. I am writing it down, but did not have
enough time yet (the time frame is weeks). But there is no published proof
that delta=4 is currect neither :)
> I haven't checked the trim changes.
> I haven't checked the union*/diff*/hedge* changes.
These two points are also connected -- replace a lambda functions
performing comparison (with possibly infinity element) by a Maybe bound.
The paper cites the improvement of performance, I do not recall now.
Cheers,
Milan
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4342#comment:16>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
