August 2010 - Libraries

Adding manual worker/wrapper transforms to Data.Map
by Johan Tibell 20 Aug '10

20 Aug '10

Hi all, I tried doing the "standard" worker/wrapper transform to some functions in Data.Map. For example, by transforming insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a insertWith' f k x m = insertWithKey' (\_ x' y' -> f x' y') k x m -- | Same as 'insertWithKey', but the combining function is applied strictly. insertWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a insertWithKey' f kx x t0 = case t of Tip -> singleton kx $! x Bin sy ky y l r -> case compare kx ky of LT -> balance ky y (insertWithKey' f kx x l) r GT -> balance ky y l (insertWithKey' f kx x r) EQ -> let x' = f kx x y in seq x' (Bin sy kx x' l r) to insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a insertWith' f k x m = insertWithKey' (\_ x' y' -> f x' y') k x m {-# INLINE insertWith' #-} insertWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a insertWithKey' f kx x t0 = kx `seq` go t0 where go t = case t of Tip -> singleton kx $! x Bin sy ky y l r -> case compare kx ky of LT -> balance ky y (go l) r GT -> balance ky y l (go r) EQ -> let x' = f kx x y in seq x' (Bin sy kx x' l r) {-# INLINE insertWithKey' #-} I got a 16% speedup on this benchmark: {-# LANGUAGE BangPatterns #-} module Main where import Criterion.Main import qualified Data.Map as M main = defaultMain [ bench "insertWith20k/size" $ whnf (M.size . insertWith) n ] where -- Number of elements n = 20000 insertWith :: Int -> M.Map Int Int insertWith max = go 0 M.empty where go :: Int -> M.Map Int Int -> M.Map Int Int go n !m | n >= max = m | otherwise = go (n + 1) $ M.insertWith' (+) (n `mod` 20) n m There are lots of other functions in Data.Map that could benefit from the same transform, in particular some of the folds. Does anyone see a reason for me to not go ahead and try to create a patch that performs this transformation on all functions that could benefit from it? I would include a Criterion benchmark that shows the gains. Cheers, Johan

5 8

xformat feedback
by Simon Michael 19 Aug '10

19 Aug '10

Hi Sean, thanks for http://hackage.haskell.org/package/xformat, found via http://www.serpentine.com/blog/2009/09/25/riddle-me-this . It sounded like the easy way to get that problem solved. Here's what I was thinking as I tried to use it: "Would it kill you to include *one* example in the package or haddock docs ?!" Sorry, but you did ask for comments to improve it. :) I found out more at http://github.com/spl/xformat/tree/master/tests/ . What I was hoping for was a way to do printf, without the variable arguments which make reuse troublesome, but still using standard printf format strings. Does this lib do that ? Best - Simon

1 0

One more possible fix of Data.Map
by Kazu Yamamoto 19 Aug '10

19 Aug '10

Hello, The comment of Data.Map says: Note: in contrast to Adam's paper, we use (<=) comparisons instead of (<) comparisons in [join], [merge] and [balance]. Quickcheck (on [difference]) showed that this was necessary in order to maintain the invariants. It is quite unsatisfactory that I haven't been able to find out why this is actually the case! Fortunately, it doesn't hurt to be a bit more conservative. I tested Data.Map much and found: - Test of [difference] does not stand for delta 5 with (>) instead of (>=) - But stands for delta 4 with (>) instead of (>=) To implement Adams's paper (in page 9) correctly, the "balance" function should use (>) instead of (>=): balance :: k -> a -> Map k a -> Map k a -> Map k a balance k x l r | sizeL + sizeR <= 1 = Bin sizeX k x l r | sizeR > delta*sizeL = rotateL k x l r -- here | sizeL > delta*sizeR = rotateR k x l r -- and here | otherwise = Bin sizeX k x l r where sizeL = size l sizeR = size r sizeX = sizeL + sizeR + 1 This is because Adams defines balanced as follows: size left <= w * size right size right <= w * size left When balanced, rotation is not necessary. I push my test environment to github: http://github.com/kazu-yamamoto/bst/ Here is usage: Please edit delta in Data/Map/Internal.hs. The balance function already use (>). % cd test % runghc -i.. TestMap.hs --maximum-generated-tests=10000 -t difference P.S. I think Milan said relating thing: http://article.gmane.org/gmane.comp.lang.haskell.libraries/13448 --Kazu

1 0

ANN: primes-0.2.0.0
by Sebastian Fischer 16 Aug '10

16 Aug '10

Hello, I have uploaded new versions of the primes package to Hackage: http://hackage.haskell.org/package/primes Version 0.2.0.0 significantly improves the memory requirements (and as a result also the run time) compared to 0.1.1. The run time is now almost linear and when streaming an infinite list of primes the memory requirements are almost constant. I think, primes is now the most efficient prime generator on Hackage. The interface has been generalised to support arbitrary Integral types and not just Integers and I have added two convenience functions: isPrime :: Integral int => int -> Bool primeFactors :: Integral int => int -> [int] These functions can be used for numbers with moderately large prime factors but are impractical when passing RSA numbers [1] because they simply use trial division [2]. The performance improvements have also been implemented in version 0.1.1.1 which provides the old interface. As the only API changes (of 0.2) are additions and the generalisation to Integral types, switching directly to 0.2 should be straightforward. The implementation is similar to Melissa O'Neil's code on the Haskell Wiki [3] which is one of the most efficient (pure) prime generators (without an upper bound) in Haskell that I know of. My goal was to simplify her implementation without sacrificing performance significantly. The performance of the prime package now almost matches the performance of Melissa's code. Judge for yourself whether you find the implementation more readable: http://github.com/sebfisch/primes/blob/0.1.1.1/Data/Numbers/Primes.hs The 0.2 tarball contains (source, not binary) programs that can be used to measure the performance of my implementation using Criterion (runtime.hs) and checking the memory requirements when generating large primes (memory.hs). Cheers, Sebastian [1]: http://en.wikipedia.org/wiki/RSA_numbers [2]: http://en.wikipedia.org/wiki/Trial_division [3]: http://www.haskell.org/haskellwiki/Prime_numbers -- Underestimating the novelty of the future is a time-honored tradition. (D.G.)

1 0

[PATCH] Add strict versions of insertWith and insertWithKey to IntMap
by Johan Tibell 15 Aug '10

15 Aug '10

Hi, I needed a strict version of insertWith on IntMaps in one of my projects. I added both insertWith' and insertWithKey' for consistency with Data.Map. I didn't bump the version number as I assume this is done just before release rather by the first patch that mandates an increase according to the PVP. Since this is an API addition the third version number should be bumped. Who applies patches to containers? Sun Aug 15 12:28:52 CEST 2010 Johan Tibell <johan.tibell(a)gmail.com> * Add strict versions of insertWith and insertWithKey to IntMap -- Johan

2 2

Fwd: Warning: message 1OjHiX-00070x-Aj delayed 48 hours
by John Goerzen 13 Aug '10

13 Aug '10

Does anybody know what's going on there? This is the email address on Hackage. -------- Original Message -------- Subject: Warning: message 1OjHiX-00070x-Aj delayed 48 hours Date: Fri, 13 Aug 2010 16:19:05 -0500 From: Mail Delivery System <Mailer-Daemon(a)complete.org> To: jgoerzen(a)complete.org This message was created automatically by mail delivery software. A message that you sent has not yet been delivered to one or more of its recipients after more than 48 hours on the queue on glockenspiel.complete.org. The message identifier is: 1OjHiX-00070x-Aj The date of the message is: Wed, 11 Aug 2010 15:16:02 -0500 The subject of the message is: Another API stability plea The address to which the message has not yet been delivered is: quickcheck(a)projects.haskell.org Delay reason: SMTP error from remote mail server after end of data: host projects.haskell.org [72.249.126.23]: 451 Temporary local problem - please try later No action is required on your part. Delivery attempts will continue for some time, and this warning may be repeated at intervals if the message remains undelivered. Eventually the mail delivery software will give up, and when that happens, the message will be returned to you.

2 1

Viability of having a new top-level "Graph" module namespace
by Ivan Lazar Miljenovic 13 Aug '10

13 Aug '10

As part of an attempt at resolving the FGL vs inductive-graphs naming mess, one solution that Edward Kmett and I thrashed out will involve utilising a new top-level module namespace of Graph.* instead of using Data.Graph.* as currently found in FGL. However, Don Stewart recommended that I ask of the collective wisdom that is the libraries mailing list before moving ahead with this proposal. The three main reasons for such a new top-level namespace are: * Avoid module clashes (ala mtl and monads-{fd,tf}): for my still-vapourware graph classes library I would have to use Data.Graph.Classes or some such due to Data.Graph being used by the containers library; the new library Thomas Bereknyei are working on can then use Graph.Inductive to avoid clashing with FGL's Data.Graph.Inductive. * Reduce the length of module names: this reason might not mean as much and the net benefit would be minimal, but something like Graph.Inductive.Algorithms.Directed is a bit nicer than Data.Graph.Inductive.Algorithms.Directed * Not all graph-related modules are necessarily strictly about data-types, etc. (and I can't find any distinction about what defines the Data.* namespace anyway); e.g. my graphviz library currently uses Data.GraphViz.*, though it should arguably go under Graphics.* instead (it's currently under Data.* because that's how I found it when I took over maintainership). So, am I able to start using Graph as a new top-level namespace? The end goal is that eventually all graph-related libraries will use this namespace (whereas currently most such libraries use Data.Graph.*, graphviz being the notable exception). -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com IvanMiljenovic.wordpress.com

6 11

Questions about iteratee package
by Edward Z. Yang 13 Aug '10

13 Aug '10

Hello John (and libraries@), I've been learning about iteratees for the past few days or so, and I couldn't help but notice that you and Oleg have named some of the iteratee types differently in your respective modules. For example, Oleg consitently refers to Enumeratees for vertical composition, while the iteratee package appears to name them EnumeratorN. This is quite a hamper to users (including myself) who go to Oleg's documents for information about how to use iteratee, as you suggest. Is there any hope of renaming some of these types, or perhaps at least documenting the discrepancies accordingly? I'd be willing to submit some patches. Cheers, Edward

5 7

#4189: Add (<.>) operator (generalizing (.) to Functor)
by Maciej Marcin Piechotka 06 Aug '10

06 Aug '10

The proposal is to add (<.>) function to Data.Functor/Control.Applicative: (<.>) :: (b -> c) -> (a -> f b) -> a -> f c f <.> g = fmap f . g -- (<.>) = (.) . fmap In intend it is related to <$> in the same way as (.) is related to $: (a . b . c) d = a $ b $ c $ d (a <.> b <.> c) d = a <$> b <$> c <$> d a is not specialized to f a to allow such chaining: const 1 <.> print <=< (read :: String -> Int) <.> readFile :: (Num t) => FilePath -> IO t Discussion deadline: 31th August 2010

10 25

Bug in Data.Map
by Daniel Peebles 05 Aug '10

05 Aug '10

Hi all! Taylor Campbell found a bug in Data.Map but wasn't able to post to this mailing list so I'm submitting this on his behalf. ---------------------------- Deletion in Data.Map does not always preserve the balance of a tree. Deletion in Data.Set appears to preserve the balance in some cases where Data.Map does not; I don't know whether Data.Set always leaves the tree balanced. I have attached two files to test the balance of trees after a random sequence of insertions and a pathological sequence of deletions (deleteMin -- although this is not pathological for some applications such as priority queues). TestMap.hs reliably demonstrates for me that deleteMin readily yields an unbalanced tree, if I supply a size of 10000 to test_map. TestSet.hs does not. The salient difference between Data.Set and Data.Map, I believe, is the choice of delta (w in Adams' paper), which is 4 in Data.Set and 5 in Data.Map. Since Adams' paper claims that when alpha (i.e. 1/ratio) is 1/2, w must exceed about 4.646, this seems suspect. But I haven't analyzed the reasoning in Adams' paper to find whether his conclusions are wrong. What I do know is that I can break trees when w is 5, but I have not been able to break them when w is 4. I also noticed a comment in Set.hs saying that a value of 4 for w improved performance on many operations. I have also not been able to break trees if I change deletion to use join rather than balance. But that slows everything down a good deal more, I believe, than simply changing w from 5 to 4.

5 6