March 2009 - Haskell-Cafe

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

02 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".

3 2

A foray into type-level programming, and getting stuck
by George Pollard 02 Mar '09

02 Mar '09

Okay, so I've written a small library to generalize 'fst' and 'snd' to arbitrary tuples, but I'd like to extend it a bit. I'm using the type-level library to do the thinking :) Imports and defines first: > {-# LANGUAGE UnicodeSyntax, MultiParamTypeClasses, > FunctionalDependencies, FlexibleInstances, FlexibleContexts, > UndecidableInstances, DeriveDataTypeable, OverlappingInstances, > ScopedTypeVariables #-} > import Prelude hiding ((-),Eq) > import qualified Prelude as P > import Data.TypeLevel.Num.Sets > import Data.TypeLevel.Num.Reps > import Data.TypeLevel.Num.Aliases > import Data.TypeLevel.Bool > import Data.TypeLevel.Num.Ops > import Data.Typeable I start by requiring that if you can access element 'n', you should be able to access element 'n-1'. > class (ImplementsPrev t n a) ⇒ Nthable t n a | t n → a where > nth ∷ n → t → a > > class (Pos n) ⇒ ImplementsPrev t n a > instance (Pred n n', Nthable t n' a') ⇒ ImplementsPrev t n a > instance ImplementsPrev t D1 a So, this is a simple induction. Testing it with the nthable instances confirms that it works; removing either of the first two lines stops the code from compiling, hurrah! > instance Nthable (a,b,c) D1 a where nth _ (a,_,_) = a > instance Nthable (a,b,c) D2 b where nth _ (_,b,_) = b > instance Nthable (a,b,c) D3 c where nth _ (_,_,c) = c Now, I have heard talk/suggestions of revamping tuples in Haskell to a more flexible system. Perhaps we would like to do it like this (modulo strictness annotations): > data (Nat n) ⇒ Tuple n a b = Tuple a b > deriving (Show,Read,Typeable,P.Eq,Ord) > infixr 0 `comma` > -- comma :: a -> (b ~> c) -> (a ~> (b ~> c)) -- to investigate > comma ∷ (Succ n n') ⇒ a → Tuple n b c → Tuple n' a (Tuple n b c) > x `comma` y = Tuple x y > empty ∷ Tuple D0 () undefined > empty = Tuple () undefined Thus, we can create, e.g. (1 `comma` 2 `comma` empty). Now, I'd like to be able to write Nthable instances, so I start with the base case: > instance (n :>=: D1) ⇒ Nthable (Tuple n a b) D1 a where > nth _ (Tuple a _) = a This works well. However, I am really stuck on the instance for the inductive case. My first idea was this: > instance (Pred x x', Nthable b x' r) ⇒ Nthable (Tuple n a b) x r where > nth _ (Tuple _ b) = nth (undefined ∷ x') b But this doesn't work, muttering about IncoherentInstances and hidden datatypes from the type-level library. So, I turn to Haskell café for help :)

3 3

Re: [Haskell-cafe] Basic problem in Haskell language design?
by Daniel Schüssler 02 Mar '09

02 Mar '09

Hi, On Sunday 01 March 2009 14:26:42 Nicu Ionita wrote: > [...] > movesFromWord8s (f:t:ws) = (f, t) : movesFromWord8s ws > moverFromWord8s _ = [] > [...] > Are there possible solutions or workarounds? for the particular problem of having to repeat the function name, you could use "case": movesFromWord8s x = case x of f:t:ws -> (f, t) : movesFromWord8s ws _ -> [] (at the cost of one extra variable name :)) Greetings, Daniel

1 0

Take a break: write an essay for Onward! Essays
by Simon Peyton-Jones 02 Mar '09

02 Mar '09

Friends Writing papers is fun, we mostly only get to write one *kind* of paper. Here is an opportunity to write something in a totally different style: Submit an essay to Onward! Essays Deadline: 20 April 2009 http://onward-conference.org/calls/foressays An Onward! essay is a thoughtful reflection upon software-related technology. Its goal is to help the reader to share a new insight, engage with an argument, or wrestle with a dilemma. A successful essay is a clear and compelling piece of writing that explores a topic important to the software community. The subject area should be interpreted broadly, including the relationship of software to human endeavours, or its philosophical, sociological, psychological, historical, or anthropological underpinnings. An essay can be an exploration of its topic, its impact, or the circumstances of its creation; it can present a personal view of what is, explore a terrain, or lead the reader in an act of discovery; it can be a philosophical digression or a deep analysis. It can describe a personal journey, perhaps that by which the author reached an understanding of such a topic. I'm the program chair, and I'd love to get submissions from the POPL/ICFP/types community. Reflections on programming languages, types, testing, verification, software engineering, compilers, society, ... you name it. Anything to do with software. NB: Onward! is co-located with OOPSLA, but they are otherwise unrelated. OO is fine, but not required. Don't forget: 20th April. Simon PS: To get your imagination going, here are a couple of (strongly-contrasting) past essays: * Dan Grossman "The transactional memory / garbage collection analogy" http://www.cs.washington.edu/homes/djg/papers/analogy_oopsla07.pdf * Dick Gabriel "Designed as designer" http://dreamsongs.org/DesignedAsDesigner.html

2 1

Hint & Cabal Install weirdness.
by Joseph Fredette 02 Mar '09

02 Mar '09

I'm attempting to install hint, I started by doing: cabal install hint and it gives me the following error: cabal: dependencies conflict: ghc-6.10.1 requires process ==1.0.1.1 however process-1.0.1.1 was excluded because ghc-6.10.1 requires process ==1.0.1.0 So I decided to try installing it via darcs, expecting to either have it work, or boil it down to one or two dependencies that were causing the problem, my hunch was right, it boils down to the ghc-mtl package, leading to the same error as above. My question is, how can I fix this? Doing a ghc-pkg hide on either process package breaks Cabal and Haddock (among others) according to the error message, and even after that happens, cabal complains about needing ghc >= 6.6 (or 6.8, depending on which package I disable), even though I have ghc 6.10. Detailed system info follows, help me haskell-cafe-kenobi(s), you're (all) my only hope(s)! Sysinfo: Arch Linux: uname -a gives: Linux Erdos 2.6.28-ARCH #1 SMP PREEMPT Mon Feb 2 22:22:59 UTC 2009 i686 Intel(R) Celeron(R) CPU 3.06GHz GenuineIntel GNU/Linux ghc --version gives: The Glorious Glasgow Haskell Compilation System, version 6.10.1 cabal --version: cabal-install version 0.6.0 using version 1.6.0.1 of the Cabal library Thanks again, /Joe

2 2

Supplying a default implementation for a typeclass based on another class
by Svein Ove Aas 02 Mar '09

02 Mar '09

I'm in the process of writing a distributed filesystem (in haskell, yay), which of course means I'm using Binary for de/serialization. Now, that's fine enough, but for simplicity (and for wireshark), I'd like to be able to have Binary fall back on an instance based on Show/Read for any type that lacks any other Binary instance.. Well, I understand why this would be somewhere between extremely hard and impossible in haskell '98, but I'm not entirely up on all the extensions, so I thought I'd ask - given every extension implemented in ghc 6.10.1, is there any reasonable way to do this?

6 7

Re: a newbies confusion with repositories - darcs or git
by trentbuck＠gmail.com 01 Mar '09

01 Mar '09

Max Battcher <me(a)worldmaker.net> writes: > +1. For the most part this was a great email. It probably belongs > immortalized on the darcs blog and elsewhere. It could even go in the manual! I think the first two chapters of the manual should be 1. Why Darcs? 2. Quick Start ...and the stuff about compiling darcs and migrating from other VCSs moved either to the end (as appendices) or simply onto the wiki.

1 0

nubBy changed?
by Tim Newsham 01 Mar '09

01 Mar '09

Did nubBy change recently? In 6.8.2 I could generate primes as: nubBy (\a b -> b `mod` a == 0) [2..] but in 6.10.1 I have to use nubBy (\a b -> a `mod` b == 0) [2..] Is this change intentional? If so, what is the reason? Tim Newsham http://www.thenewsh.com/~newsham/

2 1

Re: [Haskell-cafe] Re: memory issues
by Martin Huschenbett 01 Mar '09

01 Mar '09

ChrisK schrieb: > Bulat is right about making Block's fields strict. > >> >> -- | Get the offsets between entries in a list >> getSizes :: [Integer] -> [Integer] >> getSizes (x:y:[]) = [y - x] >> getSizes (x:y:ys) = (y - x):(getSizes (y:ys)) > > You should change the first part to add maxSize: > > > getSizes :: [Integer] -> [Integer] > > getSizes (x:y:[]) = [y - x,maxSize] > > getSizes (x:y:ys) = (y - x):(getSizes (y:ys)) > > This avoids the ugly use of (++) below. Note that appending to a singly > linked list is a bad "code smell": But Chris' version changed semantics. It should be > getSizes :: [Integer] -> [Integer] > getSizes (x:y:[]) = [y-x,maxSize-y] > getSizes (x:y:ys) = (y-x):getSizes (y:ys) instead. But > getSizes :: [Integer] -> [Integer] > getSizes [x] = [maxSize-x] > getSizes (x:y:ys) = (y-x):getSizes (y:ys) is even better as it doesn't repeat the y-x term. Regards, Martin.

1 0

differences between Data.Array and Data.Vector
by Manlio Perillo 01 Mar '09

01 Mar '09

Hi. In Hackage there are some packages named "*array*", and others named "*vector*". What are the differences? Is available a guide to the various data structures available in Haskell? Thanks Manlio Perillo

3 3