March 2010 - Libraries

Haskell platform proposal: time-extras package
by Ashley Yakeley 22 Mar '10

22 Mar '10

All, I'd like to propose my "time-extras" package to be included in the next major release of the Haskell platform. The "time" package, which is already in the Haskell Platform, is currently restricted to Haskell 98. This means that it cannot, for instance, export instances of the Data class (since this requires Rank2 or RankN). The "time-extras" package contains functionality that would be in "time" were it not for the 98 restriction. Its version number matches that of "time". Currently, it consists only of Data instances. I am the author and maintainer of "time" and "time-extras". Everyone is invited to review this proposal, following the standard procedure for proposing and reviewing packages: http://trac.haskell.org/haskell-platform/wiki/AddingPackages You can always find the latest version of this proposal here: http://trac.haskell.org/haskell-platform/wiki/Proposals/time-extras Hackage link: http://hackage.haskell.org/package/time-extras -- Ashley Yakeley

5 9

Nested types for binomial heaps
by Jim Apple 22 Mar '10

22 Mar '10

Clever type nesting techniques for ensuring the structural correctness of binomial heaps have been invented before, including the technique that Louis Wasserman implemented so efficiently for his recent proposal http://hackage.haskell.org/trac/ghc/ticket/3909 . Perhaps these previous techniques could make the nested priority queue implementation even more efiicient. Ralf Hinze: (uses a different(?) extractMin algorithm) http://web.comlab.ox.ac.uk/oucl/work/ralf.hinze/publications/IAI-TR-98-12.p… Mirror: http://scholar.google.com/scholar?cluster=5719010893172593338 Chris Okasaki: (stores children in a difference list to make their reversal fast) http://okasaki.blogspot.com/2009/10/binomial-queues-as-nested-type.html Bertram Felgenhauer: (suggests some space savings) http://www.haskell.org/pipermail/haskell-cafe/2009-October/068351.html Mirror: http://groups.google.com/group/fa.haskell/msg/cdffdbb12b28e027 Mirror 2: http://article.gmane.org/gmane.comp.lang.haskell.cafe/65428

1 0

HP 2010.2.0.0 Beta Release Candidate
by Don Stewart 21 Mar '10

21 Mar '10

We're almost done with the spec for the HP 2010.2.0.0. A beta installer for the unix package, and the .cabal file is here: http://code.haskell.org/~dons/code/haskell-platform/snapshot/ Please check it builds, and let us know if it fails. There is one remaining update to occur before we announce the full release: a new release of cabal-install, and Duncan's working on that at Zurihac. The Mac and Windows guys can get started rolling their installers! -- Don @ Zurihac

2 1

Generalizing Network.CGI exceptions to MonadCatchIO
by Anders Kaseorg 21 Mar '10

21 Mar '10

A few things have frustrated me about Network.CGI’s exception handling. • I can’t use the new-style Exception class directly; I have to convert to and from SomeException first. • There’s no analogue of nice utilities like bracket and onException for CGI. • I can only use throwCGI and catchCGI in CGIT IO, not an arbitrary MonadCGI. One way to solve all three of these problems is using MonadCatchIO. As an added bonus, we get a much simpler definition of try/catch. Who is maintaining the CGI library these days? What do you think of this patch? (It would be possible to generalize the types even further, from SomeException to Exception e => e, but I’m worried about introducing ambiguous type variables into existing code. After this patch, new code can just use the Control.Monad.CatchIO functions directly to deal with Exception e => e.) Anders -- 8< -- From 5f9b9ca5e9faf34b36887737d820c3ca9ea76e09 Mon Sep 17 00:00:00 2001 From: Anders Kaseorg <andersk(a)mit.edu> Date: Tue, 9 Mar 2010 05:18:57 -0500 Subject: [PATCH] Generalize exception handling to an arbitrary MonadCatchIO. Signed-off-by: Anders Kaseorg <andersk(a)mit.edu> --- Network/CGI.hs | 3 ++- Network/CGI/Monad.hs | 24 ++++++++++++++---------- cgi.cabal | 2 +- 3 files changed, 17 insertions(+), 12 deletions(-) diff --git a/Network/CGI.hs b/Network/CGI.hs index 3acd0db..8ebc057 100644 --- a/Network/CGI.hs +++ b/Network/CGI.hs @@ -96,6 +96,7 @@ module Network.CGI ( import Control.Exception (Exception(..), SomeException, ErrorCall(..)) import Control.Monad (liftM) +import Control.Monad.CatchIO (MonadCatchIO) import Control.Monad.Trans (MonadIO, liftIO) import Data.Char (toUpper) import Data.List (intersperse, sort, group) @@ -175,7 +176,7 @@ redirect url = do setHeader "Location" url -- > -- > main :: IO () -- > main = runCGI (handleErrors cgiMain) -handleErrors :: CGI CGIResult -> CGI CGIResult +handleErrors :: (MonadCGI m, MonadCatchIO m) => m CGIResult -> m CGIResult handleErrors = flip catchCGI outputException -- diff --git a/Network/CGI/Monad.hs b/Network/CGI/Monad.hs index 69d7840..f3d55cf 100644 --- a/Network/CGI/Monad.hs +++ b/Network/CGI/Monad.hs @@ -27,13 +27,14 @@ module Network.CGI.Monad ( throwCGI, catchCGI, tryCGI, handleExceptionCGI, ) where -import Control.Exception as Exception (SomeException, try, throwIO) +import Prelude hiding (catch) +import Control.Exception as Exception (SomeException, throwIO) import Control.Monad (liftM) +import Control.Monad.CatchIO (MonadCatchIO, block, catch, try, unblock) import Control.Monad.Error (MonadError(..)) import Control.Monad.Reader (ReaderT(..), asks) import Control.Monad.Writer (WriterT(..), tell) import Control.Monad.Trans (MonadTrans, MonadIO, liftIO, lift) -import Data.Monoid (mempty) import Data.Typeable (Typeable(..), Typeable1(..), mkTyConApp, mkTyCon) @@ -66,6 +67,11 @@ instance Monad m => Monad (CGIT m) where instance MonadIO m => MonadIO (CGIT m) where liftIO = lift . liftIO +instance MonadCatchIO m => MonadCatchIO (CGIT m) where + CGIT m `catch` h = CGIT (try m) >>= either h return + block (CGIT m) = CGIT (block m) + unblock (CGIT m) = CGIT (unblock m) + -- | The class of CGI monads. Most CGI actions can be run in -- any monad which is an instance of this class, which means that -- you can use your own monad transformers to add extra functionality. @@ -92,7 +98,7 @@ runCGIT (CGIT c) = liftM (uncurry (flip (,))) . runWriterT . runReaderT c -- * Error handling -- -instance MonadError SomeException (CGIT IO) where +instance MonadCatchIO m => MonadError SomeException (CGIT m) where throwError = throwCGI catchError = catchCGI @@ -103,17 +109,15 @@ throwCGI = liftIO . throwIO -- | Catches any expection thrown by a CGI action, and uses the given -- exception handler if an exception is thrown. -catchCGI :: CGI a -> (SomeException -> CGI a) -> CGI a -catchCGI c h = tryCGI c >>= either h return +catchCGI :: (MonadCGI m, MonadCatchIO m) => m a -> (SomeException -> m a) -> m a +catchCGI = catch -- | Catches any exception thrown by an CGI action, and returns either -- the exception, or if no exception was raised, the result of the action. -tryCGI :: CGI a -> CGI (Either SomeException a) -tryCGI (CGIT c) = CGIT (ReaderT (\r -> WriterT (f (runWriterT (runReaderT c r))))) - where - f = liftM (either (\ex -> (Left ex,mempty)) (\(a,w) -> (Right a,w))) . try +tryCGI :: (MonadCGI m, MonadCatchIO m) => m a -> m (Either SomeException a) +tryCGI = try {-# DEPRECATED handleExceptionCGI "Use catchCGI instead." #-} -- | Deprecated version of 'catchCGI'. Use 'catchCGI' instead. -handleExceptionCGI :: CGI a -> (SomeException -> CGI a) -> CGI a +handleExceptionCGI :: (MonadCGI m, MonadCatchIO m) => m a -> (SomeException -> m a) -> m a handleExceptionCGI = catchCGI diff --git a/cgi.cabal b/cgi.cabal index fba15ff..b2ba0c1 100644 --- a/cgi.cabal +++ b/cgi.cabal @@ -30,7 +30,7 @@ Library Extensions: MultiParamTypeClasses ghc-options: -Wall - Build-depends: network>=2.0, parsec >= 2.0, mtl >= 1.0, xhtml >= 3000.0.0 + Build-depends: network>=2.0, parsec >= 2.0, mtl >= 1.0, MonadCatchIO-mtl, xhtml >= 3000.0.0 If flag(split-base) Build-depends: base >= 3 && < 5, old-time, old-locale, containers Else -- 1.7.0.2

4 7

Asynchronous exceptions and laziness bugs in Data.Unique.newUnique
by Bas van Dijk 19 Mar '10

19 Mar '10

Hello, I just browsed over the source of Data.Unique.newUnique[1]: newUnique :: IO Unique newUnique = do val <- takeMVar uniqSource let next = val+1 putMVar uniqSource next return (Unique next) I think asynchronous exceptions should be blocked. Currently if an asynchronous exception is thrown after taking the MVar, putMVar is not executed anymore, leaving the MVar in the empty state. A subsequent call to newUnique will then dead-lock when it tries to take the MVar. Another problem is the laziness of 'next'. When you put 'next' in the MVar you actually put the thunk 'val+1' not an Integer in WHNF. When you create say a million uniques the last unique will be a very large thunk like 0+1+1...+1. Forcing that thunk (when you print the hash of the unique for example) will probably overflow your stack. The attached patch adds the necessary block and strictly evaluates the next unique value. regards, Bas [1] http://haskell.org/ghc/docs/latest/html/libraries/base-4.2.0.0/src/Data-Uni…

2 3

Haskell Platform: Updates to package spec for 2010.1.0.0. Time to start testing installers!]
by Don Stewart 18 Mar '10

18 Mar '10

----- Forwarded message from Don Stewart <dons(a)galois.com> ----- Date: Sat, 13 Mar 2010 13:33:44 -0800 From: Don Stewart <dons(a)galois.com> To: Haskell-platform(a)community.haskell.org Subject: Updates to package spec for 2010.1.0.0. Time to start testing installers! The testing set of packages for our first 2010 release is now in. Check http://code.haskell.org/haskell-platform/haskell-platform.cabal A number of things changed, and it is time to start testing your installers, to make sure these all hold together properly for the release due next week. Some highlights .Tools: haddock => 2.6.0 alex => 2.3.2 cabal-install => 0.8.0 Compiler: 6.12.1 (though 6.12.2 may be due this week...) Core libraries: -- array ==0.3.0.0 -- base ==4.2.0.0 and ==3.0.3.2 -- bytestring ==0.9.1.5 -- bin-package-db ==0.0.0.0 -- NEW -- Cabal ==1.8.0.2 -- containers ==0.3.0.0 -- directory ==1.0.1.0 -- extensible-exceptions ==0.1.1.1 -- NEW -- filepath ==1.1.0.3 -- ghc-binary ==0.5.0.2 -- NEW -- ghc-prim ==0.2.0.0 -- haskell98 ==1.0.1.1 -- hpc ==0.5.0.4 -- integer-gmp ==0.2.0.0 -- NEW -- integer-simple ==0.1.0.0 -- NEW -- old-locale ==1.0.0.2 -- old-time ==1.0.0.3 -- pretty ==1.0.1.1 -- process ==1.0.1.2 -- random ==1.0.0.2 -- syb ==0.1.0.2 -- template-haskell ==2.4.0.0 -- time ==1.1.4 -- MOVED BACK -- unix ==2.4.0.0 -- utf8-string ==0.3.4 -- NEW -- Win32 ==2.2.0.1 Obsoleted, and no longer provided by GHC: -- integer ==0.1.0.1 -- packedstring ==0.1.0.1 Others: cgi ==3001.1.7.2, fgl ==5.4.2.2, GLUT ==2.1.2.1, -- NOTE haskell-src ==1.0.1.3, html ==1.0.1.2, HUnit ==1.2.2.1, mtl ==1.1.0.2, network ==2.2.1.7, OpenGL ==2.2.3.0, -- NOTE parallel ==2.2.0.1, parsec ==2.1.0.1, -- NOTE QuickCheck ==2.1.0.3, regex-base ==0.93.1, regex-compat ==0.92, regex-posix ==0.94.1, stm ==2.1.1.2, xhtml ==3000.2.0.1, zlib ==0.5.2.0, HTTP ==4000.0.9 _______________________________________________ Haskell-platform mailing list Haskell-platform(a)projects.haskell.org http://projects.haskell.org/cgi-bin/mailman/listinfo/haskell-platform ----- End forwarded message -----

4 4

Re: Feedback request: priority queues in containers
by Louis Wasserman 18 Mar '10

18 Mar '10

> > I suspect the following might be faster: > > data BinomForest2 a = Empty > | NonEmpty a [BinomTree2 a] > > data BinomTree2 a = BinomTree2 a [BinomTree2 a] > > This eliminates the "Skip" constructor, which contributes only to the > nested type guarantee. > Ehehehe. This is something I'm pretty proud of inventing, because your implementation is actually significantly *slower*. The reason is essentially that I can do a lot more constructor unpacking when I have access to that much type information about the structure of the tree at each level. You didn't quite implement it correctly, because among other things, we *need* to track tree rank, at least for the roots, if it's not encoded in the type. Here are your data types, with everything unpacked as much as possible. data BinomQueue a = Nil | Cons {-# UNPACK #-} !Int {-# UNPACK #-} !(BinHeap a) (BinomQueue a) -- equivalent to [(Int, BinHeap a)], but unrolled -- we only need to track ranks in the roots data BinomSubtree a = Nil' | Cons' {-# UNPACK #-} !(BinHeap a) (BinomSubtree a) -- equivalent to [BinHeap a], but unrolled data BinHeap a = Bin a (BinomSubtree a) I tested, and this implementation actually performs better if the spine is maintained lazily, so we'll test that version. The full implementation (that is, the basic methods: insert, extract, fromList, toAscList) of your approach was attached to the ticket here<http://hackage.haskell.org/trac/ghc/attachment/ticket/3909/QuickBinom.hs>. Feel free to ghc-core it, or tinker with the implementation, but I've done a fair bit of tinkering, and my results haven't changed. Running a benchpress test on heapsorting 25000 Ints, calling performGC after every run of each method. SBinomial stands for "sparse binomial heap," which is your approach. With -O2, +RTS -H128m: min mean +/-sd median max Binomial: 0.000 3.440 2.204 4.000 8.001 SBinomial: 24.001 28.562 5.600 28.001 48.003 (ratio: 8.3x slower average) With -O2: min mean +/-sd median max Binomial: 4.000 8.801 2.606 8.001 24.002 SBinomial: 32.002 41.763 8.007 42.003 64.004 (ratio: 4.7x slower average) Without optimization, with +RTS -H128m: min mean +/-sd median max Binomial: 4.001 10.041 3.140 8.001 20.002 SBinomial: 64.004 76.805 8.790 76.005 100.006 (ratio: 7.6x slower average) Without optimization: Binomial: 12.000 19.761 5.328 16.001 40.002 SBinomial: 72.004 90.126 11.906 88.006 120.008 (ratio: 4.6x slower average) These times are measured in milliseconds. Conclusion: my implementation is *massively faster*, by a factor of at least 4.5x. (I spent the last half hour trying to optimize SBinomial -- it really is that big a difference, and it's not going to change.) Here's why I think that's the case: even though we might have the Skip constructor, how many Skip constructors are there, total? On average, half the forest is made up of Skips, so there are 1/2 log n Skip values there. But the thing is that the sparse binomial tree representation can't do anywhere near as much unpacking; in particular, the set of children of each node is not a single-constructor type. That's an O(n) increase in allocation, all for an O(log n) shortening of the spine. That's why it's a bad plan. Most of the work is being done in allocations of nodes in the *trees,* rather than along the spine among the roots. In this area, the crazy, type-system-exploiting approach actually does much less allocation, because it can do a lot more constructor unpacking. Let's test this hypothesis: My type-magical implementation, -O2, +RTS -sstderr (no -H128m this time): 3,050,272,052 bytes allocated in the heap 240,340,552 bytes copied during GC 1,087,992 bytes maximum residency (201 sample(s)) 53,136 bytes maximum slop 3 MB total memory in use (0 MB lost due to fragmentation) Generation 0: 5703 collections, 0 parallel, 0.48s, 0.53s elapsed Generation 1: 201 collections, 0 parallel, 0.22s, 0.24s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 4.52s ( 4.74s elapsed) GC time 0.70s ( 0.77s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 5.23s ( 5.51s elapsed) %GC time 13.5% (13.9% elapsed) Alloc rate 674,200,547 bytes per MUT second Productivity 86.5% of total user, 82.2% of total elapsed The sparse binomial forest representation, same options: 5,612,965,672 bytes allocated in the heap 563,671,500 bytes copied during GC 1,967,576 bytes maximum residency (202 sample(s)) 107,212 bytes maximum slop 5 MB total memory in use (1 MB lost due to fragmentation) Generation 0: 10602 collections, 0 parallel, 1.60s, 1.67s elapsed Generation 1: 202 collections, 0 parallel, 0.28s, 0.30s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 6.52s ( 6.51s elapsed) GC time 1.87s ( 1.97s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 8.40s ( 8.48s elapsed) %GC time 22.3% (23.2% elapsed) Alloc rate 860,302,018 bytes per MUT second Productivity 77.7% of total user, 76.9% of total elapsed Furthermore, if we actually profile the sparse forest representation, we confirm that a *huge* amount of allocation is being done during tree melding. Conclusion: the type-magical binomial heap implementation does a lot less allocating, and is faster even ignoring GC time. I encourage you to test it out for yourself, but I think you'll find similar results. =D Louis

4 7

FW: Feedback request: priority queues in containers
by Simon Peyton-Jones 17 Mar '10

17 Mar '10

Dear Library colleagues It's not very easy to find http://haskell.org/haskellwiki/Library_submissions, the Haskell library submission process. Starting at haskell.org I thought that the "standard libraries" link should do the job, but it doesn't. Maybe the standard libraries link should lead to a page that points to the Haddock stuff but also gives other info such as how to submit changes? I don't believe I know how to edit the main page, or even if I should, so I'm just emailing the suggestion Simon From: Louis Wasserman [mailto:wasserman.louis@gmail.com] Sent: 16 March 2010 13:41 To: Simon Peyton-Jones Subject: Re: Feedback request: priority queues in containers Bah. Have done this before, but a while ago, and I couldn't find the page reminding me of the specific details of what to do for library submissions. Thanks! Louis Wasserman wasserman.louis(a)gmail.com<mailto:wasserman.louis@gmail.com> http://profiles.google.com/wasserman.louis On Tue, Mar 16, 2010 at 8:34 AM, Simon Peyton-Jones <simonpj(a)microsoft.com<mailto:simonpj@microsoft.com>> wrote: Louis: If you want to propose changes to standard libraries, there's a well-documented procedure. (Of course, if you just want to release a package of your own there's no procedure!) http://haskell.org/haskellwiki/Library_submissions Simon From: glasgow-haskell-users-bounces(a)haskell.org<mailto:glasgow-haskell-users-bounces@haskell.org> [mailto:glasgow-haskell-users-bounces@haskell.org<mailto:glasgow-haskell-users-bounces@haskell.org>] On Behalf Of Louis Wasserman Sent: 16 March 2010 13:29 To: glasgow-haskell-users(a)haskell.org<mailto:glasgow-haskell-users@haskell.org> Subject: Feedback request: priority queues in containers Hey, I'd like to request some more feedback on the proposed<http://hackage.haskell.org/trac/ghc/ticket/3909> implementation for priority queues in containers. Mostly, I feel like adding a new module to containers should be contentious, and there hasn't been as much griping or contention as I expected. The silence is feeling kind of eerie! I'm inclined to set a deadline of next Wednesday, Mar 24, because the ticket was started two weeks ago and the current implementation has been essentially unchanged for a week. After that point, I'll consider the patch final. The proposed implementation benchmarked competitively with every alternative implementation that we tested, and offers good asymptotics in nearly every operation. Specifically, we use a binomial heap, which offers * O(log n) worst-case union * O(log n) worst-case extract (this in particular was a key objective of ours) * amortized O(1), worst-case O(log n) insertion. (In a persistent context, the amortized performance bound does not necessarily hold.) This implementation seems to offer the best balance between practical performance and asymptotic behavior. Moreover, this implementation is extremely memory-efficient, resulting in better performance on large data sets. (See the ticket for benchmarks. The most accurate benchmarks are towards the end.) A couple potentially contentious design decisions: * There is no distinction between keys and priority values. A utility type Prio p a with the instance Ord p => Ord (Prio p a) is exported to allow usage of distinct keys and priority values. * Min-queues and max queues are separated the following way: * Data.PQueue.Min exports the type MinQueue. * Data.PQueue.Max exports the type MaxQueue. (This is implemented as a wrapper around MinQueue.) The method names are the same, but I think this is acceptable, because I can't think of any algorithms that use a min-queue and a max-queue separately. * Data.PQueue adds the alias type PQueue = MinQueue, so that the "default" behavior is a min-queue. These design decisions seem to be sufficient to handle most traditional uses for priority queues. In particular, this approach offers a superset of the functionality offered by Java's built-in priority queue implementation<http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html>, which makes the same design decisions, but of course, is all imperative and yucky! (Also, it offers inferior asymptotics, heh.) I made a particular effort to offer the sort of utility functions that are found in the other modules of containers. In particular, it offers: * take, takeWhile, span, and that whole family of functions. take k q returns the *list* of the top k elements, and drop k q returns the *queue* with the first k elements deleted. The rest of these methods have analogous signatures. * q !! k is equivalent to toAscList q !! k. * filter and partition are offered in O(n) time. (It's actually not obvious that my implementation actually runs in O(n) time, but I managed to prove it.) * We offer Functor, Foldable, and Traversable instances that do not respect key ordering. All are linear time, but Functor and Traversable in particular assume the function is monotonic. The Foldable instance is a good way to access the elements of the priority queue in an unordered fashion. (We also export mapMonotonic and traverseMonotonic, and encourage the use of those functions instead of the Functor or Traversable instances.) * We offer foldrAsc, foldrDesc, foldlAsc, and foldlDesc. (Descending-order operations are just implemented as duals of the ascending-order operations, for MinQueue. For MaxQueue, it's the other way around.) * Correspondingly, we export toList, toAscList, toDescList, fromList, fromAscList, fromDescList. (toList returns an *unordered* traversal, and is *not* equivalent to toAscList.) I'm really satisfied with the patch as-is, modulo maybe tinkering with the code style a little. I'm also working on an article for TMR on priority queues in Haskell, some of the different structures we considered, and particularly the new type-safety implementation I came up with for binomial heaps in the writing of this implementation. In conclusion, I want to be sure people actually like this approach! So check it out. Complaints are appreciated, but even "I think your implementation is absolutely perfect" would reassure me. =) Louis Wasserman wasserman.louis(a)gmail.com<mailto:wasserman.louis@gmail.com> http://profiles.google.com/wasserman.louis

2 1

Re: Feedback request: priority queues in containers
by Louis Wasserman 17 Mar '10

17 Mar '10

I'm not willing to do this sort of typeclass wrapper thing, primarily because nothing else in containers does -- even though we might have a Mapping type class that handles both IntMap and Map, we don't. I'm inclined to let that design choice stand, as far as containers is concerned. It would make perfect sense to write a new package with such a type class and offering instances for the containers priority queue implementations, but I prefer to stick with the style that containers already seems to use -- that is, exporting separate modules without a unifying type class, but with nearly-identical method signatures. Louis Wasserman wasserman.louis(a)gmail.com http://profiles.google.com/wasserman.louis On Tue, Mar 16, 2010 at 11:10 AM, Tyson Whitehead <twhitehead(a)gmail.com>wrote: > On March 16, 2010 09:29:06 Louis Wasserman wrote: > > I'd like to request some more feedback on the > > proposed<http://hackage.haskell.org/trac/ghc/ticket/3909>implementation > > for priority queues in containers. Mostly, I feel like > > adding a new module to containers should be contentious, and there hasn't > > been as much griping or contention as I expected. The silence is feeling > > kind of eerie! > > Not sure if this is an appropriate question at all as I haven't looked at > the > code, but would it be possible to put any primary functionality into a > class. > > I'm thinking something along the lines of how the vector code works. This > allows you to use all the higher-order functions (i.e., those implemented > using the primary functions) on a different underlying implementation. > > I've found this particularly useful in wrapping Perl data types. For the > Perl > array, all I had to do was write an class instance for the vector module, > and > I have all these higher-order functions I could use from existing code. > > It would be very nice to have had something similar to do for the hash > tables. > Even to just provide a "native haskell" immutable look into the data so > Haskell code can extract the components it needs with standard functions. > > Cheers! -Tyson > > PS: I'm still working on the wrapping, so I might change my mind as to how > useful this really is, but thought I should throw it out there. >

5 5

Re: Feedback request: priority queues in containers
by Louis Wasserman 16 Mar '10

16 Mar '10

Why not use Okasaki & Brodal's "Optimal Purely Functional Priority Queues"? They offer worst case: * O(1) union, findMin, and insert * O(lg n) deleteMin The primary reason that we don't use this implementation is, quoting from the paper you yourself linked to, > Our data structure is reasonably efficient in practice; > however, there are several competing data structures that, although > not asymptotically optimal, are somewhat faster than ours in practice. Hence, our work is primarily of theoretical interest. > The current implementation is considerably faster than Okasaki's implementation in practice, based on our benchmarks. Furthermore, the asymptotics are really pretty good, and the constant factors appear to be relatively low. I wrote a pretty efficient skew binomial heap implementation -- the first step of Okasaki's approach -- and found it was already slower than the optimized binomial heap. I'm not sure whether or not I uploaded that benchmark, though. I'll do that at some point today, just to keep everyone happy. Louis Wasserman wasserman.louis(a)gmail.com http://profiles.google.com/wasserman.louis

1 1