September 2010 - Libraries

Proposal: Add function to create new hash tables with a default size
by Jim Apple 19 Sep '10

19 Sep '10

In other some standard libraries (Java, OCaml), hash tables can be created with a user-supplied size. This avoids some resizing for users who know they will be inserting a lot of data. Data.HashTable does not expose a function to do this. This proposal changes that. For a dictionary of 5 million strings, this patch saves me about 33% of the total execution time. For 10 million strings, this patch saves me 50% of the total execution time. http://hackage.haskell.org/trac/ghc/ticket/4193

4 6

Proposal: Add showCommandForUser to process:System.Process
by Ian Lynagh 18 Sep '10

18 Sep '10

Add showCommandForUser to process:System.Process http://hackage.haskell.org/trac/ghc/ticket/4305 There are many programs (e.g. ghc and Cabal) which run other programs, and when run with -v want to show the user what they are running. The user then often wants to run the command by hand, in order to debug a problem, but this can be tricky when the command or its arguments include spaces or other characters treated specially by shells. This proposal is for a System.Process.showCommandForUser function in the process package, such that showCommandForUser cmd args can be copied and pasted directly into a shell. I would have put this in System.Cmd, except that module is earmarked to be deprecated. The code already existed within System.Process; I've just rearranged it a bit: showCommandForUser :: FilePath -> [String] -> String showCommandForUser cmd args = unwords (map translate (cmd : args)) translate :: String -> String #if mingw32_HOST_OS translate str = '"' : snd (foldr escape (True,"\"") str) where escape '"' (b, str) = (True, '\\' : '"' : str) escape '\\' (True, str) = (True, '\\' : '\\' : str) escape '\\' (False, str) = (False, '\\' : str) escape c (b, str) = (False, c : str) #else translate str = '\'' : foldr escape "'" str where escape '\'' = showString "'\\''" escape c = showChar c #endif The fallback for rawSystem is now rawSystem cmd args = system (showCommandForUser cmd args) except with hugs on Windows, where for some reason it's rawSystem cmd args = system (cmd ++ showCommandForUser "" args) which is surely wrong, but how it behaved before. Discussion period: 2 weeks, until 26 Sep 2010. Thanks Ian

6 7

Proposal: Make intersect(By) lazier and faster
by Daniel Fischer 17 Sep '10

17 Sep '10

With the current implementation of intersectBy, the calculation of intersectBy _ xs [] takes O(length xs) time, hence doesn't finish on infinite lists and evaluates to _|_ for partial lists xs (... : _|_). The proposed new implementation, intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a] intersectBy _ [] _ = [] intersectBy _ _ [] = [] intersectBy eq xs ys = [x | x <- xs, any (eq x) ys] makes this an O(1) operation, returning [] also for infinite or partial xs. The first equation retains the property intersectBy _ [] _|_ = [] Trac ticket: http://hackage.haskell.org/trac/ghc/ticket/4323 Period of discussion: Two weeks, until 30 Sep. 2010. Cheers, Daniel

4 5

Ticket #4317 (add documentation to IODeviceType)
by Dimitry Golubovsky 17 Sep '10

17 Sep '10

Hi, The conversation originally in glasgow-haskell-users. ---------- Forwarded message ---------- From: Dimitry Golubovsky <golubovsky(a)gmail.com> Date: Sep 15, 2010 9:06 AM Subject: Re: Directory-backed Handle? To: Simon Marlow <marlowsd(a)gmail.com> Cc: glasgow-haskell-users(a)haskell.org Simon, Thanks for your reply. On 9/15/10, Simon Marlow <marlowsd(a)gmail.com> wrote: > The FD implementation of Handles never makes a Handle with an IODeviceType > of Directory, because openFile is specified to raise an exception when > applied to a directory. Yes, that was the only place in the Libraries' code I found that mentions this device type (which means I haven't missed anything ;) > Alternatively we could give it a meaning as you suggest - newline-separated > file names seems like a reasonable interpretation. It looks like there is no comments in the code for the definition of IODeviceType. I have created a ticket #4317 http://hackage.haskell.org/trac/ghc/ticket/4317 providing the code comments proposed. -- Dimitry Golubovsky Anywhere on the Web

2 1

Proposal: Add left, right and strict folds to Data.Set, Data.IntMap and Data.IntSet to mimic Data.Map.
by Milan Straka 16 Sep '10

16 Sep '10

Hi, see http://hackage.haskell.org/trac/ghc/ticket/4313. The following text is the description of ticket 4313: This proposal depends on #4278 and #4280. In accordance with a poll on libraries(a)haskell.org (see point 3 of http://article.gmane.org/gmane.comp.lang.haskell.libraries/13273) I propose to add strict folds to the containers. The Data.Map is getting left, right and strict folds in #4278. This proposal adds left, right and strict folds for Set, IntMap and IntSet. The naming is a bit tricky. The folds in IntMap mimics Map (ie. foldrWithKey, foldlWithKey, foldlWithKey'; fold and foldWithKey are deprecated in favor of foldrWithKey). The folds in Set and IntSet are classic (foldr, foldl, foldl'; the old fold is deprecated in favor of foldr). The repository of the containers package with these patches (and also several others) is at http://fox.auryn.cz/darcs/containers/. The patches are also attached (including #4280).

2 1

Proposal: Further performance improvements of Data.Set
by Milan Straka 15 Sep '10

15 Sep '10

Hi, see http://hackage.haskell.org/trac/ghc/ticket/4312. The following text is the description of ticket 4312: This proposal depends on #4280. This proposal further improves the performance of Data.Set. It consists of five patches: 1. making the set datatype to store the elements evaluated (by using a bang). This is in accordance with a poll on libraries@…, see point 1) of http://article.gmane.org/gmane.comp.lang.haskell.libraries/13273 2. improvements to union and difference implementation (by eliminating high-order function) 3. improvements to balance function which is used by nearly all methods modifying a set (making one monolithic function which allows perform only one pattern-match on the tree nodes) 4. correction of the test (the Arbitrary instance could generate unbalanced trees, which the patch 3. discovered) 5. added benchmark of union, difference and intersection methods On i386 Intel Core2 and GHC 6.12.1, the improvements are delete 13.46 deleteMax 13.58 deleteMin 15.93 difference 26.17 insert 12.20 intersection 2.21 member 9.52 union 27.59 The repository of the containers package with these patches (and also several others) is at http://fox.auryn.cz/darcs/containers/. The patches are also attached (including #4280)

1 1

mtl, transformers, and monads-fd are in an unhappy place
by Bryan O'Sullivan 12 Sep '10

12 Sep '10

Hi, gents - I've lately been writing some application code that, by virtue of the libraries it uses, depends on both mtl and monads-fd. Alas, this means that I have two incompatible versions of some of the most widely used monad transformers in scope, and I have to carefully import the right version of Control.Monad.Trans: {-# LANGUAGE PackageImports #-} import qualified "mtl" Control.Monad.Trans as M import qualified "monads-fd" Control.Monad.Trans as F Then I have to be equally careful in using the right version of liftIO depending on the monad I'm working in. This is a really bad situation for some of the platform's core libraries to be in, even temporarily, as it puts a solid barrier in place to non-wizardly people due to the confusion induced, especially since the kind of code I'm writing is the kind of appealing-yet-vanilla stuff that I'd hope would simply work (using the Snap web framework and an XMPP library). Greg Collins mentioned that there's some kind of plan for mtl to become a shell package that depends on transformers and monads-fd. Given my experience, I'd consider advancing this plan and getting it into the next Haskell Platform release (and ready before GHC 7 ships) to be a matter of the utmost urgency. What kind of help can I provide you to rush this along? Regards, Bryan.

4 3

Proposal: Significant performance improvements for Data.Map
by Don Stewart 12 Sep '10

12 Sep '10

http://hackage.haskell.org/trac/ghc/ticket/4277 Proposal: Significant performance improvements for Data.Map Description Milan Straka's recent [52] Haskell Symposium paper (PDF) shed light on the containers:Data.Map library, indicating there were both algorithmic and stylistic performance improvements to be made. 52. http://research.microsoft.com/~simonpj/papers/containers/containers.pdf This proposal provides a patch that [53] dramatically improves performance across the API. Three standard techniques are applied to the code: * [54] Worker/Wrapper transformations of recursive functions with constant arguments (aka. the [55] static argument transformation). * Explicit inlining of wrapper functions. * Explicit strictness of keys to functions. 53. http://is.gd/eJHIE 54. http://www.workerwrapper.com/ 55. http://hackage.haskell.org/trac/ghc/ticket/888 Three complementary, but orthogonal patches are provided. 1. Add a testsuite, [56] with coverage data (currently 91% of top level functions, and all core functions). 2. Add a micro-benchmark suite based on [57] Criterion, for empirical evidence of improvements to each function. 3. The optimization patch itself. All 3 patches should be applied, under this proposal. 56. http://code.haskell.org/~dons/tests/containers/hpc_index.html 57. http://hackage.haskell.org/package/criterion The [58] benchmark results are very strong: * An average speedup across the core api of 47% (on intel i7 / linux 64 bit), and; * 36% on Mac / intel core 2 duo 32 bit). http://i.imgur.com/05BWe.png 58. http://is.gd/eJHIE No bugs were identified in the development of the comprehensive testsuite, which includes a large set of unit tests from [60] Kazu Yamamoto 60. http://twitter.com/kazu_yamamoto/status/22351727559 A fork of the containers package, with the 3 patches (and a version bump to make it easier to test out) is available: darcs get http://code.haskell.org/~dons/code/containers/ Separately, the patches are attached to this ticket. The consideration period is 3 weeks (before ICFP). __________________________________________________________________ Work carried out over 28/29th August, 2010 in Utrecht, NL, by Johan Tibell and Don Stewart.

6 10

darcs patch: More accurate isatty test for MinGW.
by Edward Z. Yang 09 Sep '10

09 Sep '10

1 patch for repository http://darcs.haskell.org/packages/base: Tue Sep 7 11:41:44 EDT 2010 Edward Z. Yang <ezyang(a)mit.edu> * More accurate isatty test for MinGW.

2 2

Re: Haskell Platform Proposal: add the 'text' library
by John Lato 08 Sep '10

08 Sep '10

I'd like to first say that I'm very impressed with Ian's thoroughness of review. On the API differences between Data.Text and Data.ByteString.Char8, I agree with Duncan that the Data.Text API is more natural for text-oriented work, although I'm slightly uncomfortable with the similarities between Data.Text and Data.List. Everything works the same, until it doesn't because of a minor API change you didn't notice. Would it be useful to list the API incompatibilities in the docs, either as a list or at each relevant function? Or would that just be extra noise? John > > I compared the API of Data.Text and Data.ByteString.Char8 and found a > > number of differences: > > Many of these are deliberate and sensible. The thing with text as > opposed to lists/arrays is that almost all operations you want to do > are substring based and not element based. A Unicode code point (a > Char) is sadly only roughly related to the human concept of a > character. In particular there are combining characters. So even if > you want to search or split on a particular "character" that may mean > searching for a short sequence of Chars / code points. > > So where the ByteString API followed the List api by being byte > oriented, the Text API is substring oriented. > > > BS: Â break :: (Char -> Bool) -> ByteString -> (ByteString, ByteString) > > Â Â Â breakEnd :: (Char -> Bool) -> ByteString -> (ByteString, > ByteString) > > Â Â Â breakSubstring :: ByteString -> ByteString -> (ByteString, > ByteString) > > Text: break :: Text -> Text -> (Text, Text) > > Â Â Â breakEnd :: Text -> Text -> (Text, Text) > > Â Â Â breakBy :: (Char -> Bool) -> Text -> (Text, Text) > > > > BS: Â count :: Char -> ByteString -> Int > > Text: count :: Text -> Text -> Int > > > > BS: Â find :: (Char -> Bool) -> ByteString -> Maybe Char > > Text: find :: Text -> Text -> [(Text, Text)] > > Â Â Â findBy :: (Char -> Bool) -> Text -> Maybe Char > > > > BS: Â replicate :: Int -> Char -> ByteString > > Text: replicate :: Int -> Text -> Text > > > > BS: Â split :: Char -> ByteString -> [ByteString] > > Text: split :: Text -> Text -> [Text] > > > > BS: Â span :: (Char -> Bool) -> ByteString -> (ByteString, ByteString) > > Â Â Â spanEnd :: (Char -> Bool) -> ByteString -> (ByteString, > ByteString) > > Text: spanBy :: (Char -> Bool) -> Text -> (Text, Text) > > > > BS: Â splitBy :: (Char -> Bool) -> Text -> [Text] > > Text: splitWith :: (Char -> Bool) -> ByteString -> [ByteString] > > > > BS: Â unfoldrN :: Int -> (a -> Maybe (Char, a)) -> a -> (ByteString, > Maybe a) > > Text: unfoldrN :: Int -> (a -> Maybe (Char, a)) -> a -> Text > > > > BS: Â zipWith :: (Char -> Char -> a) -> ByteString -> ByteString -> [a] > > Text: zipWith :: (Char -> Char -> Char) -> Text -> Text -> Text > > > > I think the two APIs ought to be brought into agreement. > > Perhaps. If so, then it is the ByteString.Char8 that ought to be > brought into agreement with Text, not the other way around. I think > Text is right in this area. On the other hand, perhaps it makes sense > for ByteString.Char8 to remain like the ByteString byte interface > which is byte oriented (and probably rightly so). I hope the > significance and use of ByteString.Char8 will decrease as Text becomes > more popular. ByteString.Char8 is really just for the cases where > you're handling ASCII-like protocols. >

1 0