March 2009 - Libraries

Re: Failed to install leksah. (ghc-6.10.1 requires two versions of process)
by Jürgen Nicklisch-Franken 03 Mar '09

03 Mar '09

Hallo Andy, I'm sorry but this seems to be a cabal problem to me and I'm not shure how to fix this. In leksah.cabal the prerequisite is process >=1.0.1.0. Why and how ghc can require two different versions of the process library, well I don't know. I forward your question to the ghc library and leksah mailing list and hope we get a solution. Jürgen Am Dienstag, den 03.03.2009, 13:12 +0800 schrieb Andy Stewart: > Dear developers, > > I have install ghc-6.10.1 and gtk2hs-0.10 in Debian. > When i use cabal (1.6.0.2) install leksah, i got below error: > > Resolving dependencies... > cabal: dependencies conflict: ghc-6.10.1 requires process ==1.0.1.0 however > process-1.0.1.0 was excluded because ghc-6.10.1 requires process ==1.0.1.1 > > How to fix this? > > Thanks! > > -- Andy

3 2

Re-opening #2474
by Magnus Therning 03 Mar '09

03 Mar '09

I've again bumped into the issue I raised against old-locale: http://hackage.haskell.org/trac/ghc/ticket/2474 with a library submission in http://hackage.haskell.org/trac/ghc/ticket/2626 This resulted in no discussion at all on the list ( http://www.haskell.org/pipermail/libraries/2008-September/010709.html ) so would someone with privilege push the change into old-locale? I now I've not been following up properly on this, but hopefully that won't be held against me :-) /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus＠therning．org http://therning.org/magnus identi.ca|twitter: magthe

1 0

randomIO causing stack overflow ?
by timtoorop＠quicknet.nl 02 Mar '09

02 Mar '09

Hi, I was just messing with randomIO for no particular reason, and it suddenly caused a stack overflow which would only go away after restarting ghci. Here's what I see in ghci 6.8.2 http://moonpatio.com/fastcgi/hpaste.fcgi/view?id=1642 mmorrow posted the same using ghci 6.10.1 which gave the same stack overflow Anyone got any idea what causes this funny behavior? - Tim

3 2

ANNOUNCE: tar 0.3.0.0
by Duncan Coutts 02 Mar '09

02 Mar '09

All, I'm pleased to announce a major new release of the tar package for handling ".tar" archive files. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/tar This release has a completely new and much improved API. See the hackage page for the API documentation. There are high level "all in one" functions for extracting or creating .tar files. More interestingly, it is easy to make variants by composing a pipeline. For example extracting a ".tar.gz" file is just: > Tar.unpack dir . Tar.read . GZip.decompress =<< BS.readFile tar Or creating a ".tar.bz2" file: > BS.writeFile tar . BZip.compress . Tar.write =<< Tar.pack base dir In addition it provides a full api for inspecting and constructing tar files without having to pack or unpack to local files. The functions are lazy which allows large archives to be processed in constant space. It is based on the tar handling code that has been in use in the cabal-install program for the last year or so. It has been tested on a large number of real world .tar.gz files so compatibility should be pretty good. There is also an 'htar' tool which is essentially a demo program for the tar library. It implements the common subset of the command line interface of the standard tar program, including gzip and bzip compression. Thanks to Christian Maeder for feedback on pre-release versions. Duncan

2 2

Foldable and Traversable vs. FunctorM
by Henning Thielemann 01 Mar '09

01 Mar '09

After writing some FunctorM instance for GHC-6.4, then converting them to Traversable instances for GHC-6.8, I found that most of the time, if not always, I actually needed a FunctorM instance (i.e. fmapM method), not a Traversable instance. Defining a Traversable instance requires me to also define a Foldable instance, i.e. a foldMap function. I had trees, lists and singletons extended by additional information, e.g. data PositionList a = PositionList [(Position, a)] data AsyncException e a = AsyncException (Maybe e) a However 'foldMap' cannot utilize the additional information, namely Position and (Maybe e), respectively. In the first case this is sad, in the second case I consider this bad, since it is too easy to throw away and thus ignore the exception (Maybe e). Some kind of fold is always useful on these structures, but 'foldMap' is too limited. For Traversable there is always both sequence and mapM (and their Applicative counterparts), although you need to define only one of them. However 'sequence' works on interim data structures that are not very natural. Imagine a data structure with a 'string' parameter that is intended for instantiation by String or ByteString. Now 'sequence' requires instantiations like (IO String) or (State s ByteString) which do not share common properties of String and ByteString, e.g. having a 'length' function. Although possible, those interim types look inappropriate to me. Even more, consider a data structure like StorableVector which requires certain properties of its elements. StorableVector is intended for Int, Double and other Storable types, but you cannot store (IO Double) values. This example is not practical, because the Storable restriction disallows to define both Traversable and FunctorM instances. However you see, that one cannot even imagine 'sequence' on StorableVector, whereas 'mapM' is possible, yet very inefficient (needs copying the entire vector for each added element). My conclusion is, that FunctorM was better than its reputation, and that Traversable as it is, is not what I need most of the time. What are the experiences of other Traversable users?

2 2

major speed improvement: regex-tdfa reaches 1.0.0
by ChrisK 01 Mar '09

01 Mar '09

Announcing the version 1.0.0 release of regex-tdfa. I am proud of this release. This is not just a bug fix release. It is a serious improvement in the asymptotic running time. The previous versions allowed bad combinations of pattern and searched text length to scale badly in the length of the text. Previously the worst case for text of length N was O(N^3). The new worst case asymptotic runtime scaled as O(N). There is never any backtracking. And the worst case storage space is independent of N. The package is on hackage at http://hackage.haskell.org/cgi-bin/hackage-scripts/package/regex-tdfa The darcs repository is at http://darcs.haskell.org/packages/regex-unstable/regex-tdfa/ All non-overlapping matches are found and returned, along with all captured (parenthesized) subexpressions. The result is precisely what Posix extended regular expressions are supposed to return. To be concrete, consider example text with length of N of (2^n)+2: > longInput = replicate (2^n) 'a' ++ "bc" And define 4 worst-case-scenario patterns. I wrote the code and I know how to kill it: > wcs0 = "a*b" > wcs1 = "a*c" > wcs2 = "(a|aa)*b" > wcs3 = "(a|aa)*c" wcs0 is easy. wcs1 causes the old code to backtrack. wcs2 causes the old code's storage to scale as O(N). wcs3 causes both backtracking and O(N) storage with the old code. The old code's time scales as O(N) for wcs0, O(N^2) for wcs1 and wcs2, and O(N^3) for wcs3. The new code is always O(N). The actual timings for the old code on my G4 laptop for wcs on 2^8 and 2^9 and 2^10 are: Reason:compare-tdfa chrisk$ time ./Test-TDFA-np wcs3 8 +RTS -sstderr 2>&1 | head -4 ./Test-TDFA-np wcs3 8 +RTS -sstderr Test for [Char] Right [array (0,1) [(0,(257,1)),(1,(-1,0))]] 263,776,756 bytes allocated in the heap user 0m1.017s sys 0m0.058s Reason:compare-tdfa chrisk$ time ./Test-TDFA-np wcs3 9 +RTS -sstderr 2>&1 | head -4 ./Test-TDFA-np wcs3 9 +RTS -sstderr Test for [Char] Right [array (0,1) [(0,(513,1)),(1,(-1,0))]] 1,998,647,452 bytes allocated in the heap user 0m7.083s sys 0m0.289s Reason:compare-tdfa chrisk$ time ./Test-TDFA-np wcs3 10 +RTS -sstderr 2>&1 | head -4 ./Test-TDFA-np wcs3 10 +RTS -sstderr Test for [Char] Right [array (0,1) [(0,(1025,1)),(1,(-1,0))]] 15,653,277,200 bytes allocated in the heap user 0m53.350s sys 0m2.056s The doubling of length is causing a nearly eight-fold time increase. The heap allocation is also increasing nearly eight-fold. The new code with the same input pattern and texts gives: Reason:compare-tdfa chrisk$ time ./Test-TDFA2-0.99.19-np2 wcs3 8 +RTS -sstderr 2>&1 | head -4 ./Test-TDFA2-0.99.19-np2 wcs3 8 +RTS -sstderr Test for [Char] Right [array (0,1) [(0,(257,1)),(1,(-1,0))]] 2,135,324 bytes allocated in the heap user 0m0.017s sys 0m0.017s Reason:compare-tdfa chrisk$ time ./Test-TDFA2-0.99.19-np2 wcs3 9 +RTS -sstderr 2>&1 | head -4 ./Test-TDFA2-0.99.19-np2 wcs3 9 +RTS -sstderr Test for [Char] Right [array (0,1) [(0,(513,1)),(1,(-1,0))]] 3,588,656 bytes allocated in the heap user 0m0.024s sys 0m0.017s Reason:compare-tdfa chrisk$ time ./Test-TDFA2-0.99.19-np2 wcs3 10 +RTS -sstderr 2>&1 | head -4 ./Test-TDFA2-0.99.19-np2 wcs3 10 +RTS -sstderr Test for [Char] Right [array (0,1) [(0,(1025,1)),(1,(-1,0))]] 6,345,436 bytes allocated in the heap user 0m0.038s sys 0m0.018s Note that the heap allocation for the 1026 character example above is 2466 times less than the old code. That was too fast to prove the scaling, so take more input: Reason:compare-tdfa chrisk$ time ./Test-TDFA2-0.99.19-np2 wcs3 20 +RTS -sstderr 2>&1 | head -4 ./Test-TDFA2-0.99.19-np2 wcs3 20 +RTS -sstderr Test for [Char] Right [array (0,1) [(0,(1048577,1)),(1,(-1,0))]] 5,708,574,848 bytes allocated in the heap user 0m26.023s sys 0m0.985s Reason:compare-tdfa chrisk$ time ./Test-TDFA2-0.99.19-np2 wcs3 21 +RTS -sstderr 2>&1 | head -4 ./Test-TDFA2-0.99.19-np2 wcs3 21 +RTS -sstderr Test for [Char] Right [array (0,1) [(0,(2097153,1)),(1,(-1,0))]] 11,416,354,056 bytes allocated in the heap user 0m52.656s sys 0m1.985s The length and time both doubled, as did the heap allocation. And the new code has searched two million characters in the time the old code searched one thousand. How about away from the worst case scenario? On the testing suite the new code is running slightly slower: Reason:compare-tdfa chrisk$ time ./Test-TDFA-np -r 1 100 > /dev/null user 0m4.841s sys 0m3.019s Reason:compare-tdfa chrisk$ time ./Test-TDFA2-0.99.19-np2 -r 1 100 > /dev/null user 0m5.970s sys 0m3.012s So that is an increase of execution time of 14%. This small dip in performance might be reclaimable with more optimization. I think the gain in worst case performance already offsets the slight cost. The code for String is complete. The strict and lazy bytestrings and the (Seq Char) are currently using the String code for matching. This will be improved in a future release. Cheers, Chris The small print: regex-tdfa will still behave badly in space and time if given a pathological pattern, e.g. "(((a|aa){0,100}){0,100}){0,100}". But, I am hopeful than I can improve regex-tdfa to behave well with the patterns like this one. That is my vague goal for a future version 2.0.0 release. The very small print: I have been using ghc-6.10.1, and I think I have carried over cabal switches to make ghc-6.8.3 also work. The library probably can work with ghc-6.6, but the cabal file will need editing first as well as fixes to "Text.Regex.TDFA.NewDFA.copySTU".

1 0