- Libraries - Haskell.org

Re: xformat feedback
by Simon Michael 20 Aug '10

20 Aug '10

Sean - thanks very much! That helps a lot. haskell-libs was a misspelling of the libraries(a)haskell.org list, which I've taken the liberty of cc'ing once again. It's on gmane.org too. Best, -Simon On Aug 20, 2010, at 3:36 AM, Sean Leather wrote: > Ha! :) Yes, I was "asking for it," wasn't I? And you're absolutely > right. I gave examples in the announcement email when I asked for > feedback, but I didn't include any in the documentation. I will fix > that. > > 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 ? > > Hmm. Let me see if I can try to answer that question. > > Here's a basic example: > > *Text.XFormat.Show> showf ("Hello " % String % " #" % Num % "!") > "World" 1 > "Hello World #1!" > > As you can see, this does not use the "standard printf format > string." Instead, it uses a type-indexed function 'showf' to produce > a new function 'showf ("Hello " % String % " #" % Num % "!")' that > allows only certain types for arguments. To help see this, here is > that type: > > *Text.XFormat.Show> :t showf ("Hello " % String % " #" % Num % "!") > showf ("Hello " % String % " #" % Num % "!") :: (Num a) => String -> > a -> String > > Thus, we have a type-safe printf. > > One option that I have considered is writing a quasiquoter to allow > you to do standard printf format strings, but I haven't found a > round tuit for that, yet. > > Hope this answers your question. Thanks for bringing this up. > xformat needs some TLC after a long time. I just didn't know how it > would be used and what direction to take it in. > > BTW, what is haskell-libs(a)haskell.org ? I've never seen that before. > > Regards, > Sean

1 0

Bringing the IntMap API up to par with the Map API
by Johan Tibell 20 Aug '10

20 Aug '10

There are a few functions on Maps that could be implemented on IntMaps but aren't: - deleteAt - elemAt - updateAt - findIndex - lookupIndex The above 5 functions can be efficiently implemented on Maps in O(log n) time, as the size of the subtrees are known, but not not on IntMaps. We could still provide O(n) versions for IntMap. What's the use case for indexed lookup in maps? I've never seen it in other languages. - foldlWithKey - foldrWithKey - insertWith' - insertWithKey' - mapKeys - mapKeysMonotonic - mapKeysWith - toDescList I believe these should these should be straightforward to implement. I suggest we add these functions to IntMap so one doesn't it's a "no brainer" to switch from Maps to IntMaps for int keys. Are there any other functions that should be added to both APIs e.g. strict updateWith functions? Cheers, Johan

8 16

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