- Libraries - Haskell.org

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 03 Mar '10

03 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

Proposed addition to stm: atomicallyIO and afterCommit
by Simon Marlow 25 Feb '10

25 Feb '10

John Lauchbury has proposed the following addition to Control.Concurrent.STM. John's proposal is below, comments welcome. Personally I'm in two minds about this. It certainly captures a useful idiom, but it fails the "don't name compositions" test, and one of the additions is just a renaming of 'return', which makes it hard to justify. Cheers, Simon ----- I find I often write STM code with the structure: do ... IO code ... v <- atomically $ do ... STM code ... if ..... then do ... STM code ... return (Left ...) else do ... STM code ... return (Right ...) case v of Left ... -> ... IO actions ... Right ... -> ... IO actions ... where I have to communicate the result of choices inside STM code to corresponding code in the outer IO monad. This means that two separate parts of the code have to be kept in sync. In this simple case it's merely irritating. With larger and more complex structures it can be quite tricky to keep right. Now I use the functions 'atomicallyIO' and 'afterCommit', and can structure the code as do ... IO code ... v <- atomicallyIO $ do ... STM code ... if ..... then do ... STM code ... afterCommit $ ... IO actions ... else do ... STM code ... afterCommit $ ... IO actions ... As you see, it allows the IO code to be placed in the appropriate part of the STM code, ready to be executed when that STM branch is committed. Here's the code to would be added to the STM module: ---------------------------------------------------------------------- -- 'atomicallyIO' and 'afterCommit' are useful syntactic sugar for a -- simple continuation paradigm. They allow IO code to be placed within -- the same block of STM code in which control decisions are made -- (avoiding the need to communicate those decisions with a data type -- sent to a subsequent matching case). atomicallyIO :: STM (IO a) -> IO a atomicallyIO ioSTM = join $ atomically ioSTM afterCommit :: IO a -> STM (IO a) afterCommit mIO = return mIO ---------------------------------------------------------------------- Obviously the code is very simple, but I still find it useful to name the paradigm, and to have the specific type declarations to catch errors.

4 4

Re: Status of nubOrd (Proposal #2629)
by Gwern Branwen 25 Feb '10

25 Feb '10

On Wed, Feb 24, 2010 at 4:39 PM, Barton C Massey <bart(a)cs.pdx.edu> wrote: > I think in the end everyone agreed that putting nubOrd in > Data.Set (and nubInt in Data.IntSet?) would be a good thing. > I just never got it done; I was burned out by the process, > and I really struggled with getting Darcs to produce a > reasonable-sized patch that could be submitted. That sounds odd. You ask for help in #darcs? > I'll pick it up again if folks want, or someone else can. > I've attached a nubOrd patch I had lying around; it's > against ancient libraries and isn't even a context diff, but > it should be sufficient to reconstruct what needs to be > done. It includes QuickCheck tests and benchmarked as quite > fast IIRC. > Some of the false positives in sort.txt, BTW, will be > because the values often need to be sorted anyway. > In this case, the speed win of nubOrd over > (map head . group . sort) isn't so clear---it probably > depends on the degree of replication in the input list. > Somebody should do some benchmarking, probably. On the > other hand, nubOrd preserves the input ordering, which is > occasionally handy. Looking over the various versions of 'nub' I've collected and my notes, I wonder if we might not be best off with 3 nubs: the current stable Eq, a stable Ord (using Sets), and an unstable Ord. > I have to wonder if some sort of nubOrdWith that uses a > specified equality test wouldn't be a good thing also, Hm. Seems kind of redundant with the Eq typeclass, and I don't think I saw any uses which were equivalent to nubOrdWith. > but I > hate to spend any more time beating on this proposal. > > Bart Massey > bart(a)cs.pdx.edu It just needs someone to take the time to put together a criterion benchmark module and figure out which of the bikesheds are best. It only took a year or so for Control.Monad.void, so no reason we couldn't have faster nubs in the 2011 GHC, -- gwern

1 0

Proposal #2629: Data.List: Replace nub; add nubOrd, nubInt, nubWith
by Bart Massey 24 Feb '10

24 Feb '10

http://hackage.haskell.org/trac/ghc/ticket/2629 Everyone always complains about nub, but nobody ever does anything about it except (map head . group . sort), which isn't lazy and isn't always faster. :-) I've implemented a new function nubWith that takes a "stop list" as an argument and filters its target list against the stop list. I've then re-implemented nub and implemented nubOrd and nubInt in terms of nubWith: the stop list is a typeclass, so these implementations are trivial and new implementations are easily added. nubBy is left alone, since there's nothing obvious to be done about it. All of the nubs are still fully lazy. Basic QuickCheck tests are provided, and pass. Performance benchmarking code is provided. The performance of my nub implementation is quite comparable to that of the standard one. My nubOrd and nubInt implementations are dramatically faster, since they use a Set and IntSet respectively for the stop list. In particular, they are performant on long lists with long nubs, unlike the basic nub. My implementation is available via git at git://svcs.cs.pdx.edu/git/nub.git or can be browsed at http://svcs.cs.pdx.edu/gitweb?p=nub.git;a=tree and has a maybe-outdated tarball at http://svcs.cs.pdx.edu/haskell/nub.tar.gz The Nub.hs file itself is attached to the proposal. If the proposal is accepted, I will prepare a patch against current GHC library top-of-tree, but for now it seems easier for everyone to just look at the bits in their current natural habitat.

15 31

darcs patch: Monoid instance for Html
by anotheraddress＠gmx.de 20 Feb '10

20 Feb '10

Thu Feb 18 05:58:09 CET 2010 Daniel Schüssler <daniels(a)community.haskell.org> * Monoid instance for Html Will unfortunately break packages which already define their own instance. Possibly useful for use with things such as HoleyMonoid, though.

3 2

Setup doesn't know Cabal's version
by Axel Simon 18 Feb '10

18 Feb '10

Good morning, I'm currently migrating Gtk2hs to use Cabal to build. There is one issue that makes it really difficult to build Setup.hs files that work with several Cabal versions, namely that the version of Cabal itself is not passed to Setup.hs via CPP #defines. Thus, even though I can portably pre-process my Setup.hs scripts, I cannot reliably write code that works with Cabal 1.6 and 1.8. Am I missing something? Furthermore, I cannot build an executable that depends on the library being built in the same Cabal file. Is that intentional? Cheers, Axel.

1 0

ANN: vector 0.5
by Roman Leshchinskiy 15 Feb '10

15 Feb '10

Hi everyone, I am pleased to announce the release of version 0.5 of package vector, a high-performance Haskell array library with a powerful loop fusion framework. The main highlights compared to previous versions are: * DPH-style unboxed vectors (in Data.Vector.Unboxed) which use associated types to select the appropriate unboxed representation depending on the type of the elements. * A redesigned interface between mutable and immutable vectors. In particular, the popular unsafeFreeze primitive is now supported for all vector types. * Many new operations on both immutable and mutable vectors. * Significant performance improvements. The library comes with a fairly complete testsuite (mainly thanks to Max Bolingbroke) and is quite stable by now. Barring various disasters, I expect to release version 1.0 in the next 3 to 4 months. The release is accompanied by a new version of the NoSlow array benchmark suite. A few quite meaningless preliminary benchmarks are available at: http://unlines.wordpress.com/2010/02/15/vector-0-5-is-here-2 Both vector and NoSlow are on Hackage. Hackers can get the darcs repos from http://code.haskell.org/vector and http://code.haskell.org/NoSlow Enjoy! Roman

1 0

packedstring
by Jens Petersen 15 Feb '10

15 Feb '10

I needed to apply the follow patch to packedstring to install it with ghc-6.12.1 and cabal-install-0.8.0 on my machine: diff -u packedstring-0.1.0.1/packedstring.cabal\~ packedstring-0.1.0.1/packedstring.cabal --- packedstring-0.1.0.1/packedstring.cabal~ 2010-01-17 16:23:32.000000000 +1000 +++ packedstring-0.1.0.1/packedstring.cabal 2010-01-17 19:18:15.000000000 +1000 @@ -9,7 +9,7 @@ (Deprecated) Packed Strings. build-type: Simple Library - build-depends: base, array + build-depends: base >=4, array exposed-modules: Data.PackedString extensions: CPP (sorry gmail is probably going to mess I the patch header) Jens

3 2