- Libraries - Haskell.org

additions to Data.Map
by Ross Paterson 11 Aug '06

11 Aug '06

I'd like to propose the following additions to Data.Map (and IntMap): -- | /O(n)/. Map values and collect the 'Just' results. mapMaybe :: Ord k => (a -> Maybe b) -> Map k a -> Map k b -- | /O(n)/. Map keys\/values and collect the 'Just' results. mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> Map k a -> Map k b -- | /O(n)/. Map values and separate the 'Left' and 'Right' results. mapEither :: Ord k => (a -> Either b c) -> Map k a -> (Map k b, Map k c) -- | /O(n)/. Map keys\/values and separate the 'Left' and 'Right' results. mapEitherWithKey :: Ord k => (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)

2 3

Announcing regex-tre-0.66 and benchmarks
by Chris Kuklewicz 10 Aug '06

10 Aug '06

skaller wrote: > On Mon, 2006-08-07 at 20:38 +0100, Chris Kuklewicz wrote: >> skaller wrote: > >>> Wouldn't it be nice to use Ville Laurikari's TRE >>> package instead of PCRE? >>> >>> [It is also Posix compliant and drop in replacement for >>> gnu regex .. as well as supporting nice extensions] >>> >> It is possible to add support for more backends. >> The more the merrier, no need to replace anything. >> I have never heard of TRE before. > > TRE is actually based on mathematics. I have added TRE as a new backend. (I have libtre-0.7.4 on OS X, it is LGPL). And I have a benchmark, which I will now copy and paste. On "b(..?c)?d": PCRE is fast, TRE is almost as fast, the DFA (without subexpression capture) is a close 3rd. The Parsec backend is about 4 times slower, and the Posix library scales poorly, being far slower on large data sets. The code is in darcs http://evenmere.org/~chrisk/trl/head/ under regex-devel/bench Benchmark: find all matches and substring capture for "b(..?c)?d" in a one million character string on disk. Print the count, the first, and the last match (with captures). The benchmark program was, for String: > module Main(main) where > > import Text.Regex.XXX > > filename = "datafile" > regex = "b(..?c)?d" > main = do > input <- readFile filename > let a :: [[String]] > a = input =~ regex > b :: Int > b = length a > print (b,head a,last a) and for ByteString: > module Main(main) where > > import Text.Regex.XXX > import qualified Data.ByteString as B > > default (Int) > > filename = "datafile" > regex = "b(..?c)?d" > > main = do > input <- B.readFile filename > let a :: [[B.ByteString]] > a = input =~ regex > b :: Int > b = length a > print (b,head a,last a) where XXX was replaces by PCRE, Parsec, DFA, PosixRE, TRE and compile with "ghc -O2" Data file is 10^6 characters from permutations of the set "abcdbcdcdd\n" Using the 10^6 character datafile and String or ByteString. (The DFS uses a different semantics so a dot matches a newline, so the matching is different.) The output and user+sys reported by the time command: BenchPCRE (102363,["bcdcd","cdc"],["bbccd","bcc"]) total is 1.294s BenchTRE (102363,["bcdcd","cdc"],["bbccd","bcc"]) total is 2.128s BenchDFA (107811,["bcdcd"],["bbccd"]) total is 2.313s BenchParsec (102363,["bcdcd","cdc"],["bbccd","bcc"]) total is 8.094s BenchPosixRE (102363,["bcdcd","cdc"],["bbccd","bcc"]) total is 91.435s BenchBSPCRE (102363,["bcdcd","cdc"],["bbccd","bcc"]) total is 0.932s BenchBSTRE (102363,["bcdcd","cdc"],["bbccd","bcc"]) total is 1.297s BenchBSDFA (107811,["bcdcd"],["bbccd"]) total is 1.437s BenchBSParsec (102363,["bcdcd","cdc"],["bbccd","bcc"]) total is 8.496s BenchBSPosixRE (102363,["bcdcd","cdc"],["bbccd","bcc"]) total is 89.780 For 10^5 characters on String: PCRE 0.077s DFA 0.131s TRE 0.206s PosixRE 0.445s Parsec 0.825s Old Posix 43.760s (Text.Regex using splitRegex) Old Text.Regex took 43.76 seconds on 10^5 characters to do a task comparable to the one the others did (it ran splitRegex). The new PosixRE wrapping took 0.445 seconds instead. Yes it is two orders of magnitude faster, and this is because my wrapping only marshals the String to CString once. Laziness cannot be worth 2 orders of magnitude of runtime. This is why we needed a new wrapping, which has grown into the new library. On a 10^7 length data set: PCRE (979261,["bcdcd","cdc"],["bd",""]) time 17.388s TRE (979261,["bcdcd","cdc"],["bd",""]) time 17.880s DFA (1063961,["bcdcd"],["bd"]) time 21.617s Parsec (979261,["bcdcd","cdc"],["bd",""]) time 87.330s BenchBSPCRE (979261,["bcdcd","cdc"],["bd",""]) time 8.322s BenchBSTRE (979261,["bcdcd","cdc"],["bd",""]) time 12.644s BenchBSDFA (1063961,["bcdcd"],["bd"]) time 14.115s BenchBSParsec (979261,["bcdcd","cdc"],["bd",""]) time 83.395s

5 6

Cabal vs base
by Neil Mitchell 10 Aug '06

10 Aug '06

Hi, I'm interested in using Cabal to build the base library, just like any other library. Does this have any chance of working? How much work would it take? At the moment the libraries build script has broken on Windows loads of times, and if Cabal was used it would be nicer, less code, and more cross platform. I'd also like to compile libraries for Hat, Yhc and Catch, and if I can reuse cabal to do this that would be great. If this work was done, would it be possible to reduce the installation script for the full haskell.org libraries to get library, cabal config, cabal build, cabal install? So just a general question about what needs doing, who is capable of doing it, and what I can do to get it working. Thanks Neil

4 3

My documentation of System.Posix.Files
by Johan Tibell 10 Aug '06

10 Aug '06

I've started to write some docs for System.Posix.Files but before I finish that and move on to other packages in System.Posix.* it would be great with some feedback on style (and grammar/spelling of course, English is my second language). http://www.itstud.chalmers.se/~larssont/docs/System-Posix-Files.html * Currently most of the POSIX docs are rather incomplete and are in the spirit of "read the man pages". Often a function's documentation states what C function is called and very little beyond that. The man pages contains a wealth of information but: - Everyone doesn't know C (hopefully Haskell is their first language ;) ) - Everyone might not have them - It takes longer time if you have to go and look in the man pages - There might be subtle differences + They are likely to contain a more in depth information than my documentation of the library ever will! Perhaps I could still annotate each function with something like: NOTE: Uses the POSIX system call stat. Or something like that. Perhaps put a mapping of functions to C calls in the module description. * Perhaps I should put a general description of terms (symbolic links, everything is a file, etc.) in the module description? * Lots of error conditions are undocumented. I added some references to a function called throwErrnoIfMinus1_ which lives in System.Posix.Error. It is currently undocumented and frankly it looks like something that "should" be an internal function. Perhaps I could just mention which computations might throw an IOError? Cheers, Johan

2 1

cabal (./Setup.hs) options
by Conrad Parker 09 Aug '06

09 Aug '06

Hi, I like Cabal. There are a few things that I'm used to from autotools which I can't seem to find: dry-runs, uninstall and a "make distcheck" equivalent. Here's my wishlist (ie. stuff I wish someone, possibly me, would hack on ;-) Are the following planned, possible, far-fetched? ./Setup.hs -n, --dry-run For any command, does not actually do anything (build, install, modify the filesystem), but prints the steps that would be executed (ghc commandlines, install locations etc.) uninstall Removes all files and directories created by install sdist-test 1. runs sdist 2. unpacks the resulting tarball 3. runs configure --prefix=_inst build install (into given _inst) test uninstall 4. Checks that no files remain in _inst 5. Cleans up the source tmpdir 6. If all the above succeed, prints a message saying the tarball is ready for distribution cheers, Conrad.

5 6

darcs patch for fgl - Array import-fix
by Esa Ilari Vuokko 09 Aug '06

09 Aug '06

Hi, attached is a patch that allows fgl to compile after the recent Array-changes in base. I don't know if semantics are correct, but atleast it seems to build now. Best regards, --Esa New patches: [Remove now unneccesary hiding Data.Array.IO.indices Esa Ilari Vuokko <ei(a)vuokko.info>**20060809144302] { hunk ./Data/Graph/Inductive/Monad/IOArray.hs 16 -import Data.Array.IO hiding (indices) +import Data.Array.IO } Context: [Silence warnings. Ian Lynagh <igloo(a)earth.li>**20060730164944] [Remove a variable shadowing warning Ian Lynagh <igloo(a)earth.li>**20060730163933] [Version June 2006 Martin Erwig <erwig(a)eecs.oregonstate.edu>**20060718181211] [[project @ 2006-01-18 10:54:19 by simonmar] simonmar**20060118105419 Stop shadowing a variable (darcs patch from Ian Lynagh) ] [TAG Initial conversion from CVS complete John Goerzen <jgoerzen(a)complete.org>**20060112154129] Patch bundle hash: 8642b9c82dd2177887f7dfc84036d669ff94a27b

2 1

System.Posix.Process.executeFile question
by Frederik Eaton 09 Aug '06

09 Aug '06

Hi, I'm wondering what the second argument to 'executeFile' is. It's not clear from the documentation. http://www.haskell.org/ghc/docs/latest/html/libraries/unix/System-Posix-Pro… Also, it seems the documentation source is being parsed incorrectly. This is what it looks like to me: executeFile :: FilePath -> Bool -> [String] -> Maybe [(String, String)] -> IO () literal>executeFile cmd args env</literal calls one of the function>execv*</function family, depending on whether or not the current PATH is to be searched for the command, and whether or not an environment is provided to supersede the process's current environment. The basename (leading directory names suppressed) of the command is passed to function>execv*</function> as <varname>arg[0]</varname; the argument list passed to function>executeFile</function therefore begins with varname>arg[1]</varname Thanks! Frederik -- http://ofb.net/~frederik/

3 3

ANN: TextRegexLazy-0.66 devel release
by Chris Kuklewicz 08 Aug '06

08 Aug '06

(when (compilesOk) (announce newVersion)) This is a development release announcement of "TextRegexLazy" The "TextRegexLazy" package is dead. Long Live [regex-base -- interfaces ,regex-compat -- replace Text.Regex ,regex-posix -- PosixRE backend ,regex-pcre -- PCRE backend ,regex-parsec -- My lazy Haskell backend ,regex-dfa -- DFA based on modified CTKLight (LGPL) ] Note: Everything is BSD licensed except the regex-dfa engine which is LGPL. The darcs repository at http://evenmere.org/~chrisk/trl/head/ has the new version. The regex-compat package is a single Text.Regex.New module that uses regex-posix to replace Text.Regex (I cut and pasted from the Text.Regex module and re-implemented some of the functions). The old Text.Regex.Posix module is bypassed (so it could be removed in the future). Changing the dependency to a different backend is as simply as changing the import statement. Changing from String to ByteString would be a simple search-and-replace (and import Data.ByteString). The regex-posix package does not have a personal copy of the posix regex library like the copy GHC brings to Windows: http://darcs.haskell.org/packages/base/cbits/regex/ If someone can get regex-posix working on Windows, then [regex-base,regex-posix,regex-compat] will be functionally ready to be included along with GHC. TODO: * Much Haddock fixing for the new module hierarchy * Point the test cases at the new packages * Benchmark -- Chris Kuklewicz

1 0

ANN: TextRegexLazy-0.56, (=~) and (=~~) are here
by Chris Kuklewicz 02 Aug '06

02 Aug '06

Announcing: TextRegexLazy version 0.56 Where: Tarball from http://sourceforge.net/projects/lazy-regex darcs get --partial [--tag=0.56] http://evenmere.org/~chrisk/trl/stable/ License : BSD, except for DFAEngine.hs which is LGPL (derived from CTK light) Development/unstable version is at: darcs get [--partial] http://evenmere.org/~chrisk/trl/devel/ This is the version that has eaten John Meacham's JRegex library and survived to become strong. Thanks John! It now compiles against the posix regexp provided by the c library and the pcre library, in addition to the "full lazy" and the "DFA" backends. All 4 backends can accept regular expressions given as String and as ByteString. All 4 backends can run regular expressions against String and ByteString. In particular, the PosixRE and PCRE can run very efficiently against ByteString. (Though the input for the PosixRE needs to end in a \NUL character for efficiency). So there are 4*2*2 = 16 ways to use to provide input to this library. And the RegexContext class has at least 11 instances that both (=~) and (=~~) can target. So that is 4*2*2*11*2 = 352 things you can do with this library! Get your copy today! To run with cabal before 1.1.4 you will need to comment out the "Extra-Source-Files:" line in the TextRegexLazy.cabal file. The Example.hs file: > {-# OPTIONS_GHC -fglasgow-exts #-} > import Text.Regex.Lazy > import Text.Regex.Full((=~),(=~~)) -- or DFA or PCRE or PosixRE > > main = let b :: Bool > b = ("abaca" =~ "(.)a") > c :: [MatchArray] > c = ("abaca" =~ "(.)a") > d :: Maybe (String,String,String,[String]) > d = ("abaca" =~~ "(.)a") > in do print b > print c > print d This produces: > True > [array (0,1) [(0,(1,2)),(1,(1,1))],array (0,1) [(0,(3,2)),(1,(3,1))]] > Just ("a","ba","ca",["b"]) You can also use makeRegex and makeRegexOpts to compile and save a regular expression which will be used multiple times. Each of the 4 backends has a separate "Regex" data type with its own option types. For low level access, the WrapPCRE and WrapPosix modules expose a typesafe layer around the c libraries. You can query the "getVersion :: Maybe String" to see if the have been compiled into the library. It may be possible to use WrapPCRE and the UTF8 option flags to do unicode regex matching with PCRE. ( The Full and DFA backends use the Haskell unicode Char already ). Adding new types to String/ByteString is a matter of adding instances to the existing classes. Feedback and comments of any length is welcome. -- Chris Kuklewicz

2 4

darcs patch: Remove a variable shadowing warning (and 1 more)
by Ian Lynagh 01 Aug '06

01 Aug '06

Sun Jul 30 17:39:33 BST 2006 Ian Lynagh <igloo(a)earth.li> * Remove a variable shadowing warning Sun Jul 30 17:49:44 BST 2006 Ian Lynagh <igloo(a)earth.li> * Silence warnings.

4 3