March 2010 - Libraries

Fwd: Improving containers library
by Louis Wasserman 04 Mar '10

04 Mar '10

Whoops, meant to send this to the whole libraries list. What do people think of this implementation and approach? It's got O(log n) union and all. I think it could even be made stable, with some thought... Louis Wasserman wasserman.louis(a)gmail.com http://profiles.google.com/wasserman.louis ---------- Forwarded message ---------- From: Louis Wasserman <wasserman.louis(a)gmail.com> Date: Wed, Mar 3, 2010 at 8:06 PM Subject: Re: Improving containers library To: Milan Straka <fox(a)ucw.cz> Hokay, check it out: http://hackage.haskell.org/trac/ghc/ticket/3909 I just started this ticket to get going on adding priority queues to containers. I spent probably way too much time today working on implementing binomial queues in Haskell *well*. I think that while my code needs cleaning up, my data structures are just about perfect. The way I wrote it, that my program type-checks provides serious evidence that it's written correctly. data PQueue a = Empty | PQueue {-# UNPACK #-} !Int a !(BinomHeap a) -- It's based on a binomial heap augmented with a global root, so PQueue n x forest is a queue -- with size n, with global root x, and with its other elements in the binomial heap type BinomHeap a = BinomForest a () data BinomForest a ch = Nil | Skip !(BinomForest' a ch) | Cons !(Bin a ch) !(BinomForest' a ch) -- BinomForest a ch represents a binomial forest with roots having some minimum rank k, in which the keys have type 'a' -- and the set of children of a root of rank k has type 'ch'. BinomForest' a ch is the type of a binomial forest, starting at rank -- k+1. type BinomForest' a ch = BinomForest a (Children a ch) data Bin a ch = Bin a ch -- If ch corresponds to the children of a binomial node of rank k, then this is a binomial node of rank k. data Children a ch = Children {-# UNPACK #-} !(Bin a ch) ch -- At rank k, ch will have the form Children a (Children a (... (Children a ())...)) with depth k. Then values of this type, -- written out, look like Children tk1 (Children tk2 (....(Children tkk ())...)), where tki is a binomial tree of rank (k-i). -- This is exactly how the children of a binomial tree of rank k work. Observe that subtrees in Children are written in descending order of rank, while subtrees in BinomForest are written in ascending order of rank. When we delete-min on a binomial heap, we'll need to merge the children of the smallest root with the rest of the roots, but merging only works when we have two ascending-rank sequences. This might cause some problems, except for a lovely workaround: we merge the children of the smallest root into the rest of the roots as we work backwards. With laziness, we can get away without even knowing whether or not our current candidate is the smallest root. As a result, we get something that type checks perfectly -- which guarantees that roots of the correct rank are being assembled properly. Furthermore, we maintain all of the amortized bounds, without problems. I'm not entirely sure how different the performance would be in a more traditional, less type-safe implementation -- for one thing, we might be able to skip the "Skip" constructor in BinomForest, so when the heap had 2^n elements we'd only have to traverse a single root. However, this approach allows a lot of constructors to be unpacked nicely, which has nontrivial advantages, to say nothing of the correctness guarantees. Louis Wasserman wasserman.louis(a)gmail.com http://profiles.google.com/wasserman.louis On Wed, Mar 3, 2010 at 1:29 PM, Louis Wasserman <wasserman.louis(a)gmail.com>wrote: > Hehehehe. > > Actually, in retrospect, most of the data structures in containers are > relatively strict -- they typically won't defer work, and support worst-case > performance as opposed to amortized. (Sequence is the exception, but > worst-case O(log n) is much nicer than worst-case O(n)). > > My thinking now is along the lines of a relatively strict binomial heap > implementation, with maybe an extra module for pairing heaps when worst-case > runtime is less important than overall speed. > > Louis Wasserman > wasserman.louis(a)gmail.com > http://profiles.google.com/wasserman.louis > > > On Wed, Mar 3, 2010 at 1:16 PM, Milan Straka <fox(a)ucw.cz> wrote: > >> Hi, >> >> if I understand the function "fusing" correctly, you use the multi-pass >> variant of a pairing heap? Personally I thought more in the lines of >> a two-pass lazy variant of pairing heap mentioned in Okasaki's book. >> And there are skew heaps... Well, we'll let a benchmark do the judging :) >> >> Thanks, >> Milan >> >> > Yo, >> > >> > If you're interested in adding priority queues to containers, shameless >> > plug: I've got a good implementation of pairing heaps in >> > http://hackage.haskell.org/package/queuelike. It's a bit obfuscated >> right >> > now, but I'd definitely be interested in producing something that's >> actually >> > readable and usable enough to be put into containers... >> > >> > Louis Wasserman >> > wasserman.louis(a)gmail.com >> > http://profiles.google.com/wasserman.louis >> > >> > >> > On Wed, Mar 3, 2010 at 11:28 AM, <libraries-request(a)haskell.org> wrote: >> > >> > > Re: Improving containers library >> > > >> >> > _______________________________________________ >> > Libraries mailing list >> > Libraries(a)haskell.org >> > http://www.haskell.org/mailman/listinfo/libraries >> >> >

1 1

Text.PrettyPrint bug or doc bug
by Marcus D. Gabriel 04 Mar '10

04 Mar '10

Hello, The documentation for Text.PrettyPrint.HughesPJ states that vcat is the "List version of $$", but it works as the list version ($+$). In the source code, this is because vcat = reduceAB . foldr (above_' True) empty instead of vcat = reduceAB . foldr (above_' False) empty So either the documentation needs to be changed or the code. It would be nice to have both versions. Cheers, - Marcus

3 4

Re: Improving containers library
by Louis Wasserman 03 Mar '10

03 Mar '10

Yo, If you're interested in adding priority queues to containers, shameless plug: I've got a good implementation of pairing heaps in http://hackage.haskell.org/package/queuelike. It's a bit obfuscated right now, but I'd definitely be interested in producing something that's actually readable and usable enough to be put into containers... Louis Wasserman wasserman.louis(a)gmail.com http://profiles.google.com/wasserman.louis On Wed, Mar 3, 2010 at 11:28 AM, <libraries-request(a)haskell.org> wrote: > Re: Improving containers library >

4 4

Re: Subject: Re: Proposed additions to Data.Map: lookupFloor and lookupCeiling
by John Lato 03 Mar '10

03 Mar '10

> Message: 6 > Date: Wed, 3 Mar 2010 14:23:21 +0200 > From: Yitzchak Gale <gale(a)sefer.org> > Subject: Re: Proposed additions to Data.Map: lookupFloor and > lookupCeiling > > All of those approaches have the same asymptotic behavior. > The question is, how many different functions do we need > in this library to improve the coefficient in various special cases? > > Now that I have become aware of the feature creep that is > affecting this library, I am opposed to adding these functions. > Enough is enough. > > But here's another idea: put the internal workings into a separate > module called Data.Map.Internals that exports everything, > and have Data.Map re-export only the stable public API. +1 John

1 0

Re: Status of nubOrd (Proposal #2629)
by Leon Smith 02 Mar '10

02 Mar '10

On Wed, Feb 24, 2010 at 3:23 PM, Gwern Branwen <gwern0(a)gmail.com> wrote: > nub . sort (and the reverse) are very frequent. The attached sort.txt > was produced by > > find bin/ -name "*.hs" -exec sh -c "grep sort {} | grep nub && echo > {}" \; > sort.txt > > It's very crude and obviously produces lots of false positives & > negatives, but even so, there's at least >50 uses of nub . sort etc. Incidentally, data-ordlist has a nubSort implementation that's never more expensive than Data.List.sort. It's the same mergesort algorithm provided in Data.List except that it removes duplicates as it merges the lists. The library also provides a linear-time nub and nubBy on ordered lists, however this implementation is not used as part of nubSort. http://hackage.haskell.org/package/data-ordlist Best, Leon

2 2