- Haskell-Cafe - Haskell.org

Difference between Lazy ByteStrings and Strings in alex
by Jefferson Heard 14 Feb '07

14 Feb '07

It was suggested that I might derive some performance benefit from using lazy bytestrings in my tokenizer instead of regular strings. Here's the code that I've tried. Note that I've hacked the "basic" wrapper code in the Lazy version, so the code should be all but the same. The only thing I had to do out of the ordinary was write my own 'take' function instead of using the substring function provided by Data.Lazy.ByteString.Char8. The take function I used was derived from the one GHC uses in GHC.List and produces about the same code. The non-lazy version runs in 38 seconds on a 211MB file versus the lazy versions 41 seconds. That of course doesn't seem like that much, and in the non-lazy case, I have to break the input up into multiple files, whereas I don't have to in the lazy version -- this does not take any extra time. The seconds do add up to a couple of hours for me, though once I'm done, and so I'd like to understand why, when the consensus was that Data.ByteString.Lazy might give me better performance in the end, it doesn't do so here. I am running GHC 2.6 now, and am using -O3 as my optimization parameter. I'm profiling the code now, but was wondering if there was any insight... -- Jeff Non-lazy version { module Main where import qualified FileReader } %wrapper "basic" $letter = [a-zA-Z] $digit = 0-9 $alphanum = [a-zA-Z0-9] $punct = [\! \@ \# \$ \% \^ \& \*  \_ \- \+ \= \{ \[ \} \] \\ \| \; \: \' \" \, \. \? \/ \` \~] $dec = \. $posneg = [\- \+] @date1 = jan($punct|uary)?\ $digit{1,2}(\,\ $digit{2,4})? | feb($punct|ruary)?\ $digit{1,2}(\,\ $digit{2,4})? | mar($punct|ch)?\ $digit{1,2}(\,\ $digit{2,4})? | apr($punct|il)?\ $digit{1,2}(\,\ $digit{2,4})? | may?\ $digit{1,2}(\,\ $digit{2,4})? | jun($punct|e)?\ $digit{1,2}(\,\ $digit{2,4})? | jul($punct|y)?\ $digit{1,2}(\,\ $digit{2,4})? | aug($punct|ust)?\ $digit{1,2}(\,\ $digit{2,4})? | sep($punct|tember)?\ $digit{1,2}(\,\ $digit{2,4})? | sept($punct)?\ $digit{1,2}(\,\ $digit{2,4})? | oct($punct|ober)?\ $digit{1,2}(\,\ $digit{2,4})? | nov($punct|ember)?\ $digit{1,2}(\,\ $digit{2,4})? | dec($punct|ember)?\ $digit{1,2}(\,\ $digit{2,4})? @date2 = $digit{1,2} $punct $digit{1,2} $punct $digit{2,4} @time = $digit{1,2} \: $digit{2} (am|pm)? @word = $alphanum+ @number = $posneg? $digit+ | $posneg? $digit+ $dec $digit+ | $posneg? $digit+ (\,$digit{3})+ | $posneg? $digit? (\,$digit{3})+ $dec $digit+ $white = [\t\r\n\v\f\ ] @doc = \< DOC \> @tag = \< $alphanum+ \> | \<\/ $alphanum+ \> tokens :- @doc { \s -> "" } @tag ; $white+ ; @time { \s -> s } @number { \s -> s } @word { \s -> s } $punct ; . ; { printCount c [] = print c printCount c (l:ls) = if l == "" then printCount (c+1) ls else printCount c ls main = do file <- readFile "trecfile1" printCount 0 (alexScanTokens file) } -- ------------------------------------------------------------------------------------------------------------ Version depending on ByteString.Lazy -- note that the grammar is the same, so it has been omitted -- ------------------------------------------------------------------------------------------------------------ ... grammar ... { type AlexInput = (Char, -- previous char B.ByteString) -- current input string takebytes :: Int -> B.ByteString -> String takebytes (0) _ = "" takebytes n s = c : takebytes (n-1) cs where c = B.index s 0 cs = B.drop 1 s alexGetChar :: AlexInput -> Maybe (Char,AlexInput) alexGetChar (_, bytestring) | bytestring == B.empty = Nothing | otherwise = Just (c , (c,cs)) where c = B.index bytestring 0 cs = B.drop 1 bytestring alexInputPrevChar :: AlexInput -> Char alexInputPrevChar (c,_) = c alexScanTokens :: B.ByteString -> [String] alexScanTokens str = go ('\n',str) where go inp@(_,str) = case alexScan inp 0 of AlexToken inp' len act -> act (takebytes len str) : go inp' AlexSkip inp' len -> go inp' AlexEOF -> [] AlexError _ -> error "lexical error" printCount :: Int -> [String] -> IO () printCount c [] = print c printCount c (l:ls) = if l == "" then printCount (c+1) ls else printCount c ls main = do file <- B.readFile "trecfile1" printCount 0 (alexScanTokens file) }

5 5

Re: [Haskell-cafe] How to solve this problem?It's quite easy in PHP.
by dons＠cse.unsw.edu.au 14 Feb '07

14 Feb '07

keepbal: > > The code and template are separated in the PHP example,so > designers can design with out too much PHP knowledge.This is > actually what I want to solve. I'd use one of the Html/XML pretty printing libraries then, xhtml: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/xhtml-3000.0.1 haxml: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HaXml-1.13.2 hxt: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hxt-7.1 All available on hackage.haskell.org. There's few others too, here, http://www.haskell.org/haskellwiki/Libraries_and_tools/Web_programming It should be perfectly possible to write clean code, with the presentation separated from the content. -- Don

1 0

Suggestion for hackage
by Benjamin Franksen 13 Feb '07

13 Feb '07

Hi It would be a nice feature if one could look online at the documentation of a package, i.e. w/o downloading and building the package first. Fr instance, haddock generated API docs can give you a much better idea what you can expect from a library package than the mere package description. Cheers Ben

2 1

Optimization fun
by Creighton Hogg 13 Feb '07

13 Feb '07

Hello Haskell-ers, So a friend and I were thinking about making code faster in Haskell, and I was wondering if there was a way to improve the following method of generating the list of all prime numbers. It takes about 13 seconds to run, meanwhile my friend's C version took 0.1. I'd love to learn a bit more about how to optimize Haskell code. Cheers, Creighton Hogg -- Naive way to calculate prime numbers, testing each new n to see if it has prime factors less than sqrt(n). import Data.List primes = 2:(foldr (\x y -> if isPrime x then x:y else y) [] [3..]) where isPrime x = foldl' (\z y -> z && (if x `mod` y == 0 then False else True)) True (take (floor $ sqrt $ fromIntegral x) primes)

9 21

SIP & SDP parsers
by Neil Davies 13 Feb '07

13 Feb '07

Hi Has anyone out there done any work on parsers for SIP (Session Initiation Protocol) and/or SDP (Session Description Protocol)? Thought that I would ask before I embarked on it myself. Neil

1 0

[Haskell-cafe] Foldr tutorial, Inspired by Getting a Fix from a Fold
by Chris Moline 13 Feb '07

13 Feb '07

I hope the following doesn't come across as condescending... The recent issue of The Monad Reader has generated some excitement, mostly to do with the time travel article. I, however, would like to discuss a simpler solution to implementing dropWhile with foldr, which is discussed in the first article of TMR. When I was taught about folds, I was told that foldr starts at the end of the list and then builds up the result from there. But this turns out to be an unhelpful way of thinking. It's better to say foldr starts at the beginning of the list, just like foldl. But how does this work? To see, we'll start by implementing a simpler function than dropWhile, one which determines whether we should cons an element onto a list or just return the list. dropHead p x xs = if p x then xs else x:xs Note that I've funnily given a separate arg to the head of the list and to its tail. That's not a typo and later we will see why. Now let's apply dropHead to each element of the list [1, 2, 3, 4, 5]: map (dropHead p) [1, 2, 3, 4 ,5] => [dropHead p 1, dropHead p 2, dropHead p 3, dropHead p 4, dropHead p 5] Now we need to figure out where to get the second argument for each of the dropHead applications. I know! If a call to dropHead comes before another call to dropHead, we'll pass the result of the second call as the second arg of the first. And if there are no calls after a call to dropHead, we'll pass our base case as the second arg to that call. Let's have a look: threadResults basec [] = basec threadResults basec [f:fs] = f $ threadResults basec fs threadResults [] [dropHead p 1 ...] = dropHead p 1 $ dropHead p 2 $ dropHead p 3 $ dropHead p 4 $ dropHead p 5 [] Let's see it in action! First let's let our predicate determine whether a value is less than three. dropHead (< 3) 5 [] = if (< 3) 5 then [] else 5:[] => [5] dropHead (< 3) 4 [5] = if (< 3) 4 then [5] else 4:[5] => [4, 5] dropHead (< 3) 3 [4, 5] = if (< 3) 3 then [4, 5] else 3:[4, 5] => [3, 4, 5] dropHead (< 3) 2 [3, 4, 5] = if (< 3) 2 then [3, 4, 5] else 2:[3, 4, 5] => [3, 4, 5] dropHead (< 3) 1 [3, 4, 5] = if (< 3) 1 then [3, 4, 5] else 1:[3, 4, 5] => [3, 4, 5] => [3, 4, 5] Do you now see how foldr works? It starts at the beginning of the list and applies the function you gave it to the first element of the list. Then to get the second argument of the first call, it applies your function to the second element of the list and passes the result of that to the first call. In other words, it /recurs/ on the next element of the list. When we finally get to the end, the base case is passed to the final call of your function and it returns, and all the previous calls return building their results from the calls after. So in other words to implement dropWhile with foldr merely requires: dropHead p x xs = if p x then xs else x:xs dropWhile p l = foldr (dropHead p) [] l Or even simpler: dropWhile p = foldr (\x l' -> if p x then l' else x:l') [] take 3 $ dropWhile (< 5) [1..] => [5, 6, 7] No abtruse machinery required! __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

7 10

ANNOUNCE: urlcheck 0.1, (smp) parallel link checker
by dons＠cse.unsw.edu.au 13 Feb '07

13 Feb '07

This little tool has been kicking around on my harddrive for a month or two now, so time to release! I'm pleased to announce the first release of urlcheck, an parallel link checker, written in Haskell. Frustrated with the resources and time consumed by 'linkchecker', when preparing the weekly news, I coded up a lightweight, smp-capable replacement in Haskell. urlcheck pings urls found in the input file, checking they aren't 404s. It uses Haskell threads to run queries concurrently, and can transparently utilise multiple cores if you have them. Usage: $ urlcheck urlcheck.html Found 0 broken links. Checked 10 links (10 unique) in 1 file. Search time: 5 secs Get it from Hackage! http://hackage.haskell.org/cgi-bin/hackage-scripts/package/urlcheck-0.1 -- Don

1 0

Even better Eratosthenes sieve and lucky numbers
by oleg＠pobox.com 13 Feb '07

13 Feb '07

We further simplify the previously posted genuine sieve algorithm and generalize it to the finding of lucky numbers. We observe that we only need to store marks _signifying_ the integers, but never the integers themselves. Thus we arrive at the algorithm that is distinguished from all previously posted by: (i) doing no operations on composite numbers (ii) using neither multiplication nor division nor the remainder operation (iii) using neither general addition nor the comparison. The algorithm only relies on the successor, predecessor and zero comparison. The predecessor can be easily eliminated. Thus the algorithm can be used with Church and Peano numerals, or members of Elliptic rings, where zero comparison and successor take constant time but other arithmetic operations are more involved. > -- repl_every_n n l replaces every (n+1)-th element in a list (_:l) > -- with False > repl_every_n :: Int -> [Bool] -> [Bool] > repl_every_n n l = repl_every_n' n l > where repl_every_n' 0 (_:t) = False: repl_every_n n t > repl_every_n' i (h:t) = h: repl_every_n' (pred i) t > > primes = 2:(loop 3 (repeat True)) > where loop n (False:t) = loop (succ (succ n)) t > loop n (_:t) = n:(loop (succ (succ n)) (repl_every_n (pred n) t)) > > main = putStrLn $ "Last 10 primes less than 10000: " ++ > show (take 10 $ reverse $ takeWhile (< 10000) primes) Last 10 primes less than 10000: [9973,9967,9949,9941,9931,9929,9923,9907,9901,9887] The algorithm easily generalizes to lucky numbers http://mathworld.wolfram.com/LuckyNumber.html http://www.research.att.com/~njas/sequences/A000959 > -- Consider the series of odd numbers starting with k=1; the k-th number > -- is 2k-1. > -- If we start the elimination from the very beginning of the series (k=1), > -- we start with the phase (2k-2) and eliminate with the step 2k-2. > -- If we start at the number k+1, the phase becomes (2k-2-k) = (k-2). > -- Thus the starting phase gets incremented by 1 as we move up the series. > -- However, already eliminated numbers don't count, so as we skip > -- over eliminated numbers, we increment the phase by 2 > lucky = 1:(loop 3 0 (repeat True)) > where loop n i (False:t) = loop (succ (succ n)) (succ (succ i)) t > loop n i (_:t) = n:(loop (succ (succ n)) (succ i) > (repl_every_np i (pred n) t)) > > -- repl_every_np i n eliminates (marks as False) every (n+1)-th number > -- starting with the phase i. > -- Already eliminated numbers don't count. > repl_every_np :: Int -> Int -> [Bool] -> [Bool] > repl_every_np i n (False:t) = False: repl_every_np i n t > repl_every_np 0 n (_:t) = False: repl_every_np n n t > repl_every_np i n (_:t) = True: repl_every_np (pred i) n t *Main> take 10 lucky [1,3,7,9,13,15,21,25,31,33] *Main> takeWhile (<100) lucky [1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79,87,93,99]

1 0

IO is not a monad
by Yitzchak Gale 12 Feb '07

12 Feb '07

<troll> Prelude> let f .! g = ((.) $! f) $! g Prelude> let f = undefined :: Int -> IO Int Prelude> f `seq` 42 *** Exception: Prelude.undefined Prelude> ((>>= f) . return) `seq` 42 42 Prelude> ((>>= f) .! return) `seq` 42 42 </troll> Regards, Yitz

15 45

Parsec and Java
by Joel Reymont 12 Feb '07

12 Feb '07

Folks, Is there a Java parser implemented using Parsec? Thanks, Joel -- http://wagerlabs.com/

3 2