January 2007 - Libraries

lazy ByteStrings: toChunks
by Dominic Steinitz 28 Jan '07

28 Jan '07

> On 24.01 11:58, Ross Paterson wrote: > > Can you point at some examples? I had a quick look, but couldn't find > > any uses of toChunks not preceded by concat. I would expect most of > > those examples to operate on substrings that might span chunk boundaries. > > I am using toChunks for encryption and it is a very valuable tool. > Basically the task is "process each chunk of this bytestring which > might be >4gb in total". > > - Einar Karttunen Einar, I am re-writing some of the crypto library at the moment. Two questions: 1. Why not use lazy bytestrings for everything? 2. What encryption are you working on and could it supplement / replace code in the crypto library? Dominic.

2 1

ANN: regex-tdfa 0.56
by Chris Kuklewicz 28 Jan '07

28 Jan '07

Greetings, My new regular expression backend "regex-tdfa" is passing all the tests I have been throwing at it, so it is time to share the good news. First up: Where is it? Version 0.56 is in my "stable" location at > darcs get --partial darcs.haskell.org:/home/darcs/packages/regex-tdfa The version that will get updated and broken more often is "unstable" at > darcs get --partial darcs.haskell.org:/home/darcs/packages/regex-unstable/regex-tdfa It needs a slightly updated regex-base package (version >= 0.80) at > darcs get --partial darcs.haskell.org:/home/darcs/packages/regex-unstable/regex-base It has only been tested (on Max OS X) with GHC 6.6 and depends on base >= 2.0 for Data.ByteString, Data.ByteString.Lazy, and Data.Sequence. ** What does regex-tdfa do? It runs POSIX regular expression searches correctly. No other regular expression backend for Haskell does this correctly. The regular expression can be chosen to be from a String, ByteString, ByteString.Lazy, or (Data.Seq Char). Independent of that choice the searched text can also be any of those types. ** Properties and benefits of regex-tdfa: It follows a known standard: POSIX. (If you find that it disagrees with the standard then I will fix it.) It is written in Haskell, so there is no C library to compile and install. Though it is currently only written for GHC 6.6, it could be ported to any other compiler with only minor changes. (I expect that if you drop the polymorphic MPTC interface of regex-base it could be made Haskell98). It works with Unicode since it can be used on [Char] (and it works if there are '\NUL' characters around). It is lazy in the regular expression: it only builds the DFA if you use it, and only builds the state it needs, which are memoized in a lazy Trie. It is lazy in the searched text, and the pure function that searches the text only evaluates the text until the next match is done and does not hold onto the initial text. Thus you could efficiently search a [Char] up to the size of the Position type, which is an Int for now. It is free, the regex-tdfa library is under a BSD-3 license. ** Does it work? Yes. The regex-posix backend that come with GHC does not run all the searches correctly: it is buggy (example at end of announcement). And the regex-posix backend is also impossibly slow -- the slowest backend by far -- orders of magnitude slower. The regex-tre backend that wraps the TRE library has exposed this very fast library to the harsh gaze of QuickCheck. The lesson from QuickCheck is to never use regex-tre because the TRE library (version 0.7.4) is buggy. For regex-tdfa backend I took/stole ideas from Ville Laurikari's Master thesis which describes the algorithm that TRE uses. And I made a pure Haskell implementation that now passes all the tests at http://www.research.att.com/~gsf/testregex/testregex.html and follows the notes at http://www.research.att.com/~gsf/testregex/re-interpretation.html and passes those tests as well. And it "passes" QuickCheck tests which actually just compare the answers that regex-posix, regex-tre, and regex-tdfa since I do not have a bug free reference implementation to compare against. ** Why the name TDFA? Tagged Deterministic Finite Automata. The Tagged part is from Ville Laurikari's thesis work. ** Speed: If you do not care only about the match as a whole and not about subexpression matching then you can set the captureGroups ExecOption to False: makeMyRegex = makeRegex defaultCompOpt myExecOpt where myExecOpt = defaultExecOpt { captureGroups = False } And redefine (=~) and (=~~) to use makeMyRegex instead of makeRegex: (=~) :: (RegexMaker Regex CompOption ExecOption source,RegexContext Regex source1 target) => source1 -> source -> target (=~) s r = let re = makeMyRegex r :: Regex in match re s (=~~) :: (RegexMaker Regex CompOption ExecOption source,RegexContext Regex source1 target,Monad m)=> source1 -> source -> m target (=~~) s r = let re = makeMyRegex r :: Regex in match re s The benefit to this is speed, as it then proceeds to run all matches of "b(..?c)?d" against a large test file *faster* than the the TRE C library backend. My compliments to those who worked on ghc and -O2. It even runs nearly as fast as regex-dfa in this mode. Thus regex-dfa is (mostly) obsolete. If you use the default and capture the subgroups then the speed is reduced by a factor of about 4. This is because of the very simple data structures that keep track of the run time state. I intend to improve this aspect of the design now that I have a working algorithm. I have not benchmarked the speed of compiling the regular expression from the String. This compiling is done with very lazy data structures, so the DFA size is really only as big as you actually explore while running the match. ** Examples of bugs in regex-posix and regex-tre: An example for regex-posix: > *Main> "ab" Posix.=~ "((a)|(b)){2,}" :: MatchArray > array (0,3) [(0,(0,2)),(1,(1,1)),(2,(0,1)),(3,(1,1)) The array holds (group #, (match offset, match length)) The 0th group is the whole match "ab". The 2nd group is (a) and it matched the first "a" and the third group is (b) and matched the "b". But the second group is a child of the first group ((a)|(b)) which matched "b". The standard requires that captured groups are nested inside their parents, and here "a" is not not nested inside "b". So the regex-posix C backend that comes with GHC is buggy. The correct answer is, where the second group matched nothing: > *Main> "ab" TDFA.=~ "((a)|(b)){2,}" :: MatchArray > array (0,3) [(0,(0,2)),(1,(1,1)),(2,(-1,0)),(3,(1,1))] An example for regex-tre: "yyyyyy" TRE.=~ "(yyy|(x?)){2,4}" array (0,2) [(0,("yyyyyy",(0,6))),(1,("yyy",(3,3))),(2,("yyy",(3,3)))],"") Here TRE reports that the second group (x?) which should only match "" or "x" somehow matched "yyy". This is even more wrong than the regex-posix bug above. The correct answer, where the second group does not match: array (0,2) [(0,("yyyyyy",(0,6))),(1,("yyy",(3,3))),(2,("",(-1,0)))],"") -- Chris Kuklewicz

1 0

lazy ByteStrings: toChunks
by Ross Paterson 25 Jan '07

25 Jan '07

toChunks exposes the implementation, and so shouldn't be in the public interface, should it? There could be a function from lazy to ordinary ByteStrings (B.concat . toChunks), though.

4 5

Re: patch applied (packages/base): IsString is GHC-only (so why is it in the Prelude?)
by Duncan Coutts 24 Jan '07

24 Jan '07

On Tue, 2007-01-23 at 10:38 -0800, Ross Paterson wrote: > Tue Jan 23 10:30:07 PST 2007 Ross Paterson <ross(a)soi.city.ac.uk> > * IsString is GHC-only (so why is it in the Prelude?) Yes, can we please have a discussion about what's going on here. Changes to the base library are supposed to go via the libraries review process. I'm not complaining that we slipped up, I just want to make sure people can have a chance to comment. I'm cc'ing the libraries list. Duncan

5 6

ANN: polyparse-1.00
by Malcolm Wallace 24 Jan '07

24 Jan '07

polyparse-1.00 -------------- Announcing: http://www.cs.york.ac.uk/fp/polyparse PolyParse is a collection of parser combinator libraries in Haskell. They were all previously distributed as part of HaXml, but are now split out to make them more widely available. You are likely to use only one of the included modules at any one time - they are generally alternatives to each other, as well as an alternative to other widely-used parser libraries available elsewhere. * Text.Parse. The Text.Read class from Haskell'98 is widely recognised to have many problems. It is inefficient. If a read fails, there is no indication of why. Worst of all, a read failure crashes your whole program! Text.Parse is a proposed replacement for the Read class. It defines a new class, Parse, with methods that return an explicit notification of errors, through the Either type. It also defines a number of useful helper functions to enable the construction of parsers for textual representations of Haskell data structures, e.g. named fields. Unsurprisingly, Text.Parse is really just a specialisation of the Poly combinators for String input, and the entire Poly API is also re-exported. The DrIFT tool can derive instances of the Parse class for you automatically. (Use the syntax {-! derive : Parse !-}) * Text.ParserCombinators.HuttonMeijer. The most venerable of all monadic parser combinator libraries, this version dates from 1996. Originally distributed with Gofer, then Hugs, as ParseLib. It uses the idea of "failure as a list of successes" to give multiple possible parses through backtracking. (But in practice, almost nobody wants any parse except the first complete one.) * Text.ParserCombinators.HuttonMeijerWallace. The Hutton/Meijer combinators, extended to take an arbitrary token type as input (not just characters), plus a running state (e.g. to collect a symbol table, or macros), plus some facilities for simple error-reporting. * Text.ParserCombinators.Poly. The name Poly comes from the arbitrary token type. Thus, you can write your own lexer if you wish, rather than needing to encode lexical analysis within the parser itself. This is a fresh set of combinators, improving on the HuttonMeijer variety by keeping only a single success, not a list of them. This is more space-efficient, whilst still permitting backtracking. Error-handling is also much improved: there are essentially two kinds of failure, soft and hard. Soft failure just means that the current parse did not work out, but another parse might be OK. Hard failure means that no parse will succeed, because we have already passed a point of commitment. Thus you can give far more accurate error messages to the user, including multi-layered locations. * Text.ParserCombinators.PolyState is just like Poly, except it adds an arbitrary running state parameter. * Text.ParserCombinators.PolyLazy is just like Poly, except it does not return explicit failures. Instead, an exception is raised. Thus, it can return a partial parse result, before a full parse is complete. The word partial indicates that, having committed to return some outer data constructor, we might later discover some parse error further inside, so the value will be partial, as in incomplete: containing bottom. However, if you are confident that the input is error-free, then you will gain hugely in space-efficiency - essentially you can stream-process your parsed data-structure within very small constant space. This is especially useful for large structures like e.g. XML trees. * Text.ParserCombinators.PolyStateLazy combines PolyState and PolyLazy. All the Poly* variations share the same basic API, so it is easy to switch from one set to another, when you discover you need an extra facility, just by changing a single import. Regards, Malcolm

1 0

ANN: regex-* updates and regex-tdfa 0.20 first release
by Chris Kuklewicz 23 Jan '07

23 Jan '07

Greetings. I have several bits of news about regex-* packages. First: I have fixed a small bug in one instance of RegexContext, defined in Text.Regex.Contex in the regex-base class (included in GHC). The new version of regex-base is 0.80 and is available at http://darcs.haskell.org/packages/regex-unstable/regex-base/. The instance fixed was > instance (RegexLike a b) => RegexContext a b (MatchResult b) where and I doubt this affects anyone at the moment. Second: There is also a new version of regex-tre at http://darcs.haskell.org/packages/regex-unstable/regex-tre/ (version 0.81) that exposes the 'compRightAssoc' option when making a Regex (see Text.Regex.TRE.Wrap for all the options). Third: I wish to note that that the libtre backend (up to the current version 0.7.5) that regex-tre uses is buggy and that regex-tre / libtre should only be used where testing shows that no bugs are being trigged. (Why go to that much trouble? Because the libtre backend is very very fast). Fourth: The fabulous new all Haskell POSIX compatible backend! This is a first announcement of regex-tdfa, my "tagged" DFA regular expression backend. It is an implementation of regular expressions in Haskell; it does not hand off the data to a library written in c. The ultimate goal of regex-tdfa is to replace regex-posix as the default engine that come with GHC. Why go to the trouble of replacing regex-posix? Because regex-posix is very very slow (and not quite POSIX, as seen at the end of this message). The new regex-tdfa does not use the slow backtracking method like my pure Haskell backend regex-posix. It uses a deterministic finite automata, similar in spirit to one I derived from CTKlight for use in the pure Haskell regex-dfa backend (which is LGPL -- the rest are BSD-3 license). But regex-dfa is fast at a cost of not returning any parenthesized subexpression captures (i.e only \0 and not \1 \2 \3 ...). The regex-tre backend (BSD3) that uses the libtre c library (LGPL) employs a special "tagged" dfa technique to get subexpression captures while still using an efficient DFA. The regex-posix engine that comes with GHC is impossibly slow but regex-tre is very very fast and (claims to also be) a POSIX engine. I was thus inspired to create regex-tdfa which aims to create a pure Haskell variant of this tagged-DFA algorithm under a simple BSD3 license. The 0.20 version of regex-tdfa that I am announcing is available at http://darcs.haskell.org/packages/regex-unstable/regex-tdfa/ and requires the updated regex-base (version 0.80 or greater) and is setup to compile for GHC 6.6. These could be back-ported to GHC 6.4 by adding the fps package to GHC 6.4 to get Data.ByteString and removing references to Data.Sequence in the new regex-base and regex-tdfa packages. As of now, my first untuned version of the regex-tdfa backend performs about 2-3 times slower than regex-tre and the libtre c library. This also means regex-tdfa performs 3+ times faster than the regex-parsec engine. So the goal of a fast replacement for regex-posix is close to hand. The bad news: libtre has two problems, the first is that it is buggy. I have found patterns that the libtre engine does not handle correctly: the wrong match for the whole expression and/or subexpressions is returned (or it will fail to match when it should have succeeded). The second problem is that it does not always follow the POSIX standard policy in determining which possible parenthesized subexpession captures to return when there are several possibilities. My regex-tdfa engine does not have the bugs that I have found in libtre. But since it uses the same design concepts as libtre it had the same problem with not following the POSIX standard policy for capturing subexpressions. To fix this I have exteneded the tagging technique to keep enough information to follow the POSIX spec. So of all the regex-* backends, the regex-tdfa is the only one that passes all the tests that I have for POSIX compatibility. End note: The regex-posix engine, despite its name, does not follow the POSIX standard policy for capturing subexpressions. Example 1 of 2: "ab" =~ "((a?)((ab)?))(b?)" This should capture the sub ranges (0,2)(0,2)(0,0)(0,2)(0,2)(2,2) But it does capture the sub ranges (0,2)(0,1)(0,1)(1,1)(-1,-1)(1,2) The first group is (0,2) means the whole match was \0=="ab" The second group (0,2) or (0,1) means the first group "((a?)((ab)?))" should match \1=="ab" but it returns \1=="a". This first group should have been chosen for maximum length and the failure to do so is a policy violation. Example 2 of 2: "x" =~ "(.?)*" This should capture: (0,1)(0,1) But it does capture: (0,1)(1,1) The first group of (0,1) means the regex did match the whole \0=="x". But the regex-posix engine matched an extra iteration of the "(.?)" under the "*" operator against the empty string after the "x" and returned the empty capture of (1,1). This highly non-useful behavior violates POSIX policy. My regex-parsec engine follows a non-POSIX policy, in which it maximizes the length of just the captured subexpressions instead of all the subpatterns of the regular expression. This is useful and was easy to write and is easy to explain and agrees with the policy of other libraries such as Boost.Regex for C++ ( as in the third FAQ at http://www.boost.org/libs/regex/doc/faq.html ) But to replace regex-posix I need a fast POSIX policy engine, which is what regex-tnfa has now achieved. I will submit regex-tdfa to replace regex-posix once I have a stable version that has been further cleaned up and tuned. Anyone who wishes a useful performance time/spacce tuning challenge is free to help. If you have any evil or stressful examples of regular expressions, then I welcome adding them to my tests. -- Chris Kuklewicz

1 0

RandomGen, mkStdGen
by Frederik Eaton 20 Jan '07

20 Jan '07

Hi all, I'm having trouble using RandomGen with external tools (e.g. libraries written in C). StdGen has a nice function: mkStdGen :: Int -> StdGen Using this, I can write an FFI wrapper ending with type: (StdGen -> (a, StdGen)) by using the StdGen to generate an Int, and then using that to seed a foreign random number generator within C, and then at the end of the C function reading a final random number, passing it back to Haskell, and passing it to mkStdGen. This will always have the right semantics, I believe. However, there are several problems: - It only works for StdGen, not arbitrary instances of RandomGen - It "shrinks" my whole random state into an Int - so I might have 1024 bits of state in my random number generator within C, and within Haskell, but when I move between the two, everything is truncated to 32 bits. This is problematic in some applications, and as computers become faster it will be more of a concern. Thus, I suggest a new member of class RandomGen: mkRandomGen :: [Int] -> g It is similar to mkStdGen, but it takes a list of Int's so that users who want to save more bits of state across conversions can do so. Also, being a member of the RandomGen class, it can be depended on in more situations than mkStdGen. There is a question of backward compatibility with existing RandomGen instances. I think the best thing to do is provide a default definition for mkRandomGen which is an error or 'undefined'. This way, legacy code will still compile, but libraries which define RandomGen instances just won't work with new code which tries to call mkRandomGen. I don't imagine that there are many such libraries, and besides they wouldn't have been useful in any case if the code in question had been restricted to mkStdGen as it is currently. Hope I'm not missing some previous discussion. Best, Frederik Eaton -- http://ofb.net/~frederik/

2 2

Re: Data.List documentation improvements
by Andriy Palamarchuk 20 Jan '07

20 Jan '07

Not done yet. Can somebody apply the patch? Please let me know if there are reasons to not apply it. Thanks, Andriy ----- Original Message ---- From: Andriy Palamarchuk <apa3a(a)yahoo.com> To: libraries(a)haskell.org Sent: Monday, December 11, 2006 10:42:49 PM Subject: Re: Data.List documentation improvements It's not yet checked in. Any takers? Andriy ----- Original Message ---- From: Andriy Palamarchuk <apa3a(a)yahoo.com> To: libraries(a)haskell.org Sent: Wednesday, December 6, 2006 9:17:31 PM Subject: Re: Data.List documentation improvements The deadline for this update is up. Can somebody commit the changes for me? Here is the ticket with the patch: http://hackage.haskell.org/trac/ghc/ticket/1034 Andriy ____________________________________________________________________________________ Want to start your own business? Learn how on Yahoo! Small Business. http://smallbusiness.yahoo.com/r-index ____________________________________________________________________________________ Do you Yahoo!? Everyone is raving about the all-new Yahoo! Mail beta. http://new.mail.yahoo.com ____________________________________________________________________________________ TV dinner still cooling? Check out "Tonight's Picks" on Yahoo! TV. http://tv.yahoo.com/

3 2

haddock suggestion -- %{FILE}
by Conal Elliott 17 Jan '07

17 Jan '07

I pre-process my source code before handing to haddock. The %{FILE} directive for --source-comments etc uses the actual preprocessed file name rather than the the original, which is not what I want. Is this just an oversight? - Conal

4 9

Request: multiple categories for libraries
by Conal Elliott 16 Jan '07

16 Jan '07

How about multiple categories (i.e., tags) rather than single categories for libraries? - Conal

3 4