February 2007 - Haskell-Cafe

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 12 Feb '07

12 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 12 Feb '07

12 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

pythags
by phiroc＠free.fr 12 Feb '07

12 Feb '07

Hello, the "Advanced Monads" page in the Haskell Wikibook (http://en.wikibooks.org/wiki/Haskell/Advanced_monads) contains the following example of a List Monad pythags = do x <- [1..] y <- [x..] z <- [y..] guard (x^2 + y^2 == z^2) return (x, y, z) However, whenever you load that function definition into Hugs or GHCi, you get a message saying that "guard" is an undefined variable. Does anyone know why? Thanks. phiroc

4 4

Re: Re[2]: [Haskell-cafe] FFI basics
by Yitzchak Gale 12 Feb '07

12 Feb '07

Bulat Ziganshin wrote: > examples of lifting C functions into Haskell world: > > mysin :: Double -> Double > mysin = realToFrac . c_mysin . realToFrac > > -- c_mysin :: CDouble -> CDouble > > rnd :: Int -> IO Int > rnd x = do r <- c_rnd (fromIntegral x) > return (fromIntegral r) > > -- c_rnd :: CInt -> IO CInt OK, got it. I'll put that in. Thanks, Yitz

2 1

Genuine Eratosthenes sieve [Was: Optimization fun]
by oleg＠pobox.com 12 Feb '07

12 Feb '07

It has been already remarked that any algorithm of finding prime numbers that uses division or `mod` operations cannot be called (Eratosthenes) sieve. The insight of Eratosthenes is finding primes without resorting to division or multiplication. In his time, doing either of those operations was quite expensive (especially given the way numbers were written in Ancient Greece). Thus Eratosthenes devised one of the early examples of trading space for time. These days it's the other way around: it is far easier for a modern CPU to divide numbers than to access memory. So, the original algorithm is of historical interest it seems. Still, in the interest of purity, here it is, in Haskell. As the original Eratosthenes sieve, this algorithm uses only successor and predecessor operations. -- repl_every_n n l replaces every (n+1)-th element in a list (_:l) with 0 {- The following leaks memory! repl_every_n :: Int -> [Int] -> [Int] repl_every_n n l = case splitAt n l of (l1,_:l2) -> l1 ++ 0:(repl_every_n n l2) -} -- But this seems to run in constant space... repl_every_n :: Int -> [Int] -> [Int] repl_every_n n l = repl_every_n' n l where repl_every_n' 0 (_:t) = 0: repl_every_n n t repl_every_n' i (h:t) = h: repl_every_n' (pred i) t primes = 2:(loop [3,5..]) where loop l = case dropWhile (==0) l of (h:t) -> h:(loop (repl_every_n (pred h) t)) main = putStrLn $ "Last 10 primes less than 100000: " ++ show (take 10 $ reverse $ takeWhile (< 100000) primes) {- Last 10 primes less than 1000: [997,991,983,977,971,967,953,947,941,937] -} {- Last 10 primes less than 10000: [9973,9967,9949,9941,9931,9929,9923,9907,9901,9887] -} {- Last 10 primes less than 100000: [99991,99989,99971,99961,99929,99923,99907,99901,99881,99877] -}

2 1