- Libraries - Haskell.org

MonadWriter instance for ListT
by Nicolas Frisby 13 Mar '10

13 Mar '10

*> runWriter . runErrorT $ censor (filter (/=3)) $ tell [1,2,3] >> throwError "" (Left "",[1,2,3]) That's kind of weird, right? I understand why it is that way. I think this is reason enough to make censor part of the class, since it wouldn't have this short-coming if it weren't defined in terms of pass. *> let censorErrorT f (ErrorT m) = ErrorT (censor f m) *> runWriter . runErrorT $ censorErrorT (filter (/=3)) $ tell [1,2,3] >> throwError "" (Left "",[1,2]) Or is it preferable for censor and pass to misbehave in the same way?

2 1

Re: Please don't deprecate Haskell 98 modules.
by John Lato 11 Mar '10

11 Mar '10

> From: John Meacham <john(a)repetae.net> > > Please don't deprecate these modules. > Encouraging people to use bleeding edge APIs just contributes to the > already dicey problem of writing future and backwards compatible code in > Haskell, in fact, writing to haskell 98 is the _only_ option at the > moment with any ability to do so. I was originally in favor of deprecating haskell98 but didn't care enough to voice an opinion. John's argument has convinced me otherwise, so +1 to keeping haskell98. John

3 3

linking in cabal haddock (was: [Haskell] ANNOUNCE: barchart-0.1.1)
by Sebastian Fischer 09 Mar '10

09 Mar '10

[moving to libraries mailing list] Begin forwarded message: > From: Sebastian Fischer <sebf(a)informatik.uni-kiel.de> > Date: March 8, 2010 10:56:16 AM GMT+01:00 > To: Haskell <haskell(a)haskell.org> > Subject: Re: [Haskell] ANNOUNCE: barchart-0.1.1 > >> barchart is a command-line program with associated Haskell library After announcing the barchart package, I have some problems building its Haddock documentation. Firstly, > The API is not generated on Hackage because the diagrams library > cannot be built on GHC 6.12. Hence, I tried to generate it myself, but > Even with > > --html-location='http://hackage.haskell.org/packages/archive/$pkg/latest/doc/html' > > 'cabal haddock' does not generate links to the required packages. I noticed, that 'cabal haddock' does generate (external) Links to Hackage when I use the --html-location option after reinstalling all required packages *locally*. Why do I have to istall local documentation in order to get external links? Secondly, there are no Haddocks for the Diagrams library on Hackage and, hence, the links from the barchart docs to Diagrams's types are broken. I'd like to specify a custom link target for only the Diagrams package (the Diagrams website has Haddock documentation). Is this possible? Cheers, Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.)

1 1

Improving containers library
by Milan Straka 08 Mar '10

08 Mar '10

Hi all, I have started an internship in Cambridge and will spend 3 months on Haskell. One of the possible projects is improving the containers library. Things I am thinking about: - measuring the performance of existing implementations (notably Map and Set) and possibly improve them (either without or with API changes), - adding Queue and a PriorityQueue, - maybe adding a generalized trie, - maybe adding a hashtable (more like a trie of the hashes, something in the line of Ideal hash trees; and maybe a 'classic' hash modifiable in the ST monad?) I would be grateful for any comments, thoughts or wishes. Milan Straka

10 18

Progress on priority queues for containers
by Louis Wasserman 08 Mar '10

08 Mar '10

A brief update: I'm continuing to work on a priority queue implementation for containers. I've pretty much settled on a variation on a binomial heap that actually has the type-checker guarantee the correct binomial structure. It has the following properties: - Amortized O(1) insertion. There are variations (skew binomial heaps) with guaranteed O(1) insertion, but they add tremendously to the complexity of the implementation, if they work at all with this approach (I've encountered some difficulties with this approach). I think this is fine, as-is. - Worst-case O(log n) union. (If you're working in a single-threaded fashion, I am pretty convinced that you can treat union as amortized O(0), but O(log n) is pretty good in any event.) - O(1) find-min. - Worst-case O(log n) extract. The primary competing implementation is a pairing heap implementation, with the following properties: - O(1) insertion, union, and find-min, worst-case and amortized. - Amortized O(log n) extract, but worst-case O(n). If used in a persistent context, it's possible that a user could encounter a situation that performs linear-time extraction operations many times. (This is my primary concern with this implementation, especially given that containers users will be expecting a reliable data structure that won't break down.) For a simple heap sort, the pairing heap is just about twice as fast as the binomial heap, but I think having reasonable worst-case guarantees for containers users is important enough to dominate that concern. There has also been some discussion of using priority search queues -- priority queues in which you can also find previously inserted elements -- but I think this is more appropriate for a separate package, and not something that is necessarily needed by most users. I've also written a wide variety of utility functions, which you can see in the implementation here<http://hackage.haskell.org/trac/ghc/attachment/ticket/3909/containers-pqueu…>. In particular, a number of Data.List functions are modified to apply to priority queues, including take, drop, splitAt, takeWhile, dropWhile, span, break, filter, and partition. All of these are implemented asymptotically optimally. Do people have any other thoughts? Louis Wasserman wasserman.louis(a)gmail.com http://profiles.google.com/wasserman.louis

2 1

Re: Bug in Parsec.Token
by Don Stewart 05 Mar '10

05 Mar '10

derek.a.elkins: > Who is going to maintain "Parsec 4"? > > I'm completely against this. If people absolutely must have exactly > Parsec 2's implementation we can simply copy it into Parsec 3, and the > "compatibility" layer, in that case, will simply -be- Parsec 2. I've > considered this as a temporary solution for the performance issues > just so people could move to Parsec 3 dependencies, but that should > not be necessary now, and even then I considered it a much less than > ideal solution. > > If the community wants to freeze on Parsec 2, then I have no problem > renaming the package, otherwise I think it is both unnecessary and a > waste of effort. > The problem is the ongoing lack of confidence in Parsec 3's performance. The new release goes some way to addressing this, but I think this has gone unaddressed for too long. Can someone address the lingering concern with benchmarks against parsec 2? -- Don

2 1

Proposed additions to Data.Map: lookupFloor and lookupCeiling
by Leon Smith 05 Mar '10

05 Mar '10

Hi, here are two quick, modest additions to Data.Map. As Map is exported abstractly, lookupFlor can't be defined outside the library except via splitLookup and findMax. On the other hand, these implementations should be nearly the same cost as a regular lookup. Best, Leon -- | /O(log n)/. Find the greatest key that is smaller or equal -- to the given target key. This \"floor\" key is returned, along with it's -- associated value, as @'Just' (key, value)@. If the map does not have -- a key that is smaller or equal to the target key, then this function -- returns 'Nothing'. lookupFloor :: Ord k => k -> Map k a -> Maybe (k,a) lookupFloor = go Tip where go s k t = case t of Tip -> case s of Tip -> Nothing Bin _ ka a _ _ -> Just (ka,a) Bin _ ka a l r -> case compare ka k of LT -> go t k r GT -> go s k l EQ -> Just (ka,a) -- | /O(log n)/. Find the smallest key that is greater or equal -- to the given target key. This \"ceiling\" key is returned, along with it's -- associated value, as @'Just' (key, value)@. If the map does not have -- a key that is greater or equal to the target key, then this function -- returns 'Nothing'. lookupCeiling :: Ord k => k -> Map k a -> Maybe (k,a) lookupCeiling = go Tip where go s k t = case t of Tip -> case s of Tip -> Nothing Bin _ ka a _ _ -> Just (ka,a) Bin _ ka a l r -> case compare ka k of LT -> go s k r GT -> go t k l EQ -> Just (ka,a)

6 9

Bug in Parsec.Token
by Greg Fitzgerald 04 Mar '10

04 Mar '10

In Text.Parsec.Token, the list of reserved names is not necessarily sorted for case-insensitive languages. When the list of reserved names contains a string with capital letters, the 'identifier' combinator can accept identifiers that conflict with reserved names. Attached are patches for Parsec 2.1 and 3.0. Please let me know if there's anything else I can do to ensure this patch makes it to the next release of the Haskell Platform. Thanks, Greg

6 11

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