- Haskell-Cafe - Haskell.org

Re: Genuine Eratosthenes sieve [Was: Optimization fun]
by Melissa O'Neill 20 Feb '07

20 Feb '07

Sorry, I'm a little late to this thread, but the topic of > sieve [] = [] > sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x /= 0] (as posted by Rafael Almeida) is somewhat dear to my heart, as I wrote a paper about it last summer and sent it in to JFP. Still waiting for a reply though. Let's go back to the beginning with the classic complaint and the excuses... Creighton Hogg wrote: > 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. Here come the excuses, like this one from apfelmus, > While Haskell makes it possible to express very complicated > algorithms in simple and elegant ways, you have to expect to pay a > constant factor (roughly 2x-10x) when competing against the same > algorithm in low-level C. and this one from Nicolas Frisby, > I have yet to need my Haskell to perform well Matthew Brecknell came up with something much faster, namely > primes :: [Int] > primes = 2 : filter isPrime [3,5..] where > f x p r = x < p*p || mod x p /= 0 && r > isPrime x = foldr (f x) True primes FWIW, another way to write this code (without needing to think about how "fold bails early") is primes = 2: [x | x <−[3,5..], all (\p −> x `mod` p > 0) (factorsToTry x)] where factorsToTry x = takeWhile (\p −> p*p <= x) primes Both of these algorithms best the "sieve" we began with and run quickly, but as you can see (possibly more clearly from my rephrasing), this algorithm is not actually the Sieve of Eratosthenes -- it's actually a classic naive primes algorithm which checks a number for primality by trying to divide it by every prime up to its square root. But that's okay, because our initial algorithm ISN'T THE REAL SIEVE EITHER. Markus Fischmann hits the nail on the head when he says > The characteristics of a sieve is, that it uses the already found > primes to generate a list of non-primes that is then removed from a > list of candiates for primeness. But then we get distracted by a discussion about avoiding division. It's true that the real sieve avoids division, but it is NOT true that every algorithm that avoids division is the sieve. The thread ends with this algorithm from Yitzchak Gale: > -- Delete the elements of the first list from the second list, > -- where both lists are assumed sorted and without repetition. > deleteOrd :: Ord a => [a] -> [a] -> [a] > deleteOrd xs@(x:xs') ys@(y:ys') > | x > y = y : deleteOrd xs ys' > | x < y = deleteOrd xs' ys > | otherwise = deleteOrd xs' ys' > deleteOrd _ ys = ys > > sieve (x:xs) = x : sieve (deleteOrd [x+x,x+x+x..] xs) > sieve _ = [] > > primes = sieve [2..] Which seems reasonable, until you realize that every prime p we come up with is still "considered" by k deleteOrd filters, where k is the number of primes that preceeded it. So, let's recap: the original algorithm is beautiful and simple, but it is NOT the actual Sieve of Eratosthenes, NOT because it uses modulus, but because fundamentally, at the highest level, it is a different algorithm. At the risk of beating a dead horse, let's see why it's not the real sieve. What makes the sieve an efficient algorithm are the details of *what* gets "crossed off", *when*, and *how many times*. Suppose that we are finding the first 100 primes (i.e., 2 through 541), and have just discovered that 17 is prime. We will begin crossing off at 289 (i.e., 17 * 17) and cross off the multiples 289, 306, 323, ... , 510, 527, making fifteen crossings off in total. Notice that we cross off 306 (17 * 18), even though it is a multiple of both 2 and 3 and has thus already been crossed off twice. (The starting point of 17 * 17 is a pleasing, but actually *minor*, optimization for the *genuine* sieve.) The algorithm is efficient because each composite number, c, gets crossed off f times, where f is the number of unique factors of c less than sqrt(c). The average value for f increases slowly, being less than 3 for the first 10^12 composites, and less than 4 for the first 10^34. None of the algorithms we've discussed correspond to the above algorithm. It is not merely that they don't perform "optimizations", such as starting at the square of the prime, or that some of then use a divisibility check rather than using a simple increment. Rather, at a fundamental level, they all work differently than the real sieve. Following our earlier example, after finding that 17 is prime, the "phony" algorithm will check to see if 19 is divisible by 17 (in the case of Yitzchak's algorithm, divisibility is checked by comparing against 17*2), followed by 23, 29, 31, ... , 523, 527, checking a total of ninety-nine numbers for divisibility by 17. In fact, even if it did (somehow) begin at 289, it would examine all forty-five numbers that are not multiples of the primes prior to 17 (289, 293, 307, ... , 523, 527). It is also worth realizing that the set of numbers examined by the phony algorithm is not a superset of the ones examined by the real sieve (as we saw, the real algorithm crossed off 306, which the phony algorithm skips). In general, the speed of the phony algorithm depends on the number of primes that are *not* factors of each composite, whereas the speed of the real algorithm depends on the number of (unique) primes that *are*. Hopefully at this point I've piqued your interest. Maybe you're wondering what our original sieve algorithm is, if it isn't the real sieve and the mod issue is just a red herring...? Maybe you're wondering what the the real sieve looks like, coded in Haskell. Or maybe you're still not convinced about any of it. If so, I invite you to read a draft of my JFP paper, available at: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf Best Regards, Melissa.

5 7

return?
by Vikrant 20 Feb '07

20 Feb '07

Hi, I am writing a recursive function which does some IO operation. I encounter situation in which my function has to end recursion by doing "nothing" and otherwise keep calling same function with some different parameters. I did not find anything equivalent to "pass" or "return" statement in Haskell. Presently I have got a workaround. I am doing it by putting a dummy print as described below. can anybody help me in this? e.g f some_params = if some_condition then do putStr "Hacky way to do nothing!" else do perform_some_IO f some_other_params == Vikrant

3 2

trouble installing ghc 6.6: xargs: /usr/bin/ar: terminated by signal 11
by tphyahoo 20 Feb '07

20 Feb '07

I'm having trouble installing ghc 6.6. On ubuntu, virtual server (user mode linux). Something seems to be killing the process, no idea why. Anyone seen this? I looked around with ps to see if anything looked suspicious. I do have a lot of screens open, but I don't see why that should matter. There is no instance of haskell or gnci running. after running configure with no problem..... ~$ cd ghc-6.6/ ~/ghc-6.6$ sudo make &>makeOut Password: ~/ghc-6.6$ tail -n8 makeOut (echo Control/Concurrent_stub.o System/CPUTime_hsc.o System/Time_hsc.o ; /usr/bin/find Control/Applicative_split Control/Arrow_split Control/Concurrent_split Control/Concurrent/Chan_split ...long mess... Text/PrettyPrint/HughesPJ_split Text/Printf_split Text/Read_split Text/Read/Lex_split Text/Show_split Text/Show/Functions_split -name '*.o' -print) | xargs /usr/bin/ar q libHSbase.a /usr/bin/ar: creating libHSbase.a xargs: /usr/bin/ar: terminated by signal 11 make[2]: *** [libHSbase.a] Error 125 make[2]: *** Deleting file `libHSbase.a' make[1]: *** [all] Error 1 make[1]: Leaving directory `/home/thartman/ghc-6.6/libraries' make: *** [stage1] Error 2 ~/ghc-6.6$ -- View this message in context: http://www.nabble.com/trouble-installing-ghc-6.6%3A-xargs%3A--usr-bin-ar%3A… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

7 7

ANNOUNCE: nobench: Haskell implementaion benchmarks. GHC v Hugs v Yhc v NHC v ...
by dons＠cse.unsw.edu.au 20 Feb '07

20 Feb '07

Following recent discussion about a cross-implementation performance benchmark suite, based on nofib, I've gone and combined nofib with the great language shootout programs, and rewritten the build system to support cross implementation measurements. The result is: nobench http://www.cse.unsw.edu.au/~dons/nobench.html The benchmark suite runs regularly, and currently reports the speed of each program in the suite, running under each system. The results are quite interesting. The most recent run is available: http://www.cse.unsw.edu.au/~dons/nobench/bench.results http://www.cse.unsw.edu.au/~dons/nobench/bench.log The programs are a mixture of traditional nofib style Haskell, with more performance-tuned code from the shootout. More tweaking is required to help better support nhc and yhc (and jhc, and ...). The entire benchmark set and framework is available via darcs: darcs get http://www.cse.unsw.edu.au/~dons/code/nobench Currently todo are porting the rest of nofib, pretty graphs of the results (and html), and memory use measurements. Patches welcome! Cheers, Don

9 12

our worst unsafePerformIO nightmares are upon us!
by Nicolas Frisby 20 Feb '07

20 Feb '07

http://www.thinkgeek.com/geektoys/cubegoodies/86b8/ Now you can really show your coders why unsafePerformIO is to be avoided! -Nick ps - Please don't consider this post a product advertisement or endorsement of any kind.

2 1

Is lazyness make big difference?
by Nick 20 Feb '07

20 Feb '07

Hi all, (Another topic stolen from a Russian forum discussion). As everyone know, there are lot of strict languages, that have possibilities to "switch on" lazy evaluation when needed. But the examples that I saw on Haskell, there was not much use of lazy evaluation, often there were just several lazy points, and the rest could be done strictly without loss of generality. For example, in finding primes: main = print primes primes = 2:filter is_prime [3,5..] is_prime n = all (\p-> n `mod` p /= 0) (takeWhile (\p-> p*p<=n) primes) We can rewrite this in strict languages with lazy constructs. For example, in Scala (of course stream is not only lazily evaluated thing there) def main(args: Array[String]): Unit = { val n = Integer.parseInt(args(0)) System.out.println(primes(ints(2)) take n toList) } def primes(nums: Stream[Int]): Stream[Int] = Stream.cons(nums.head, primes ((nums tail) filter (x => x % nums.head != 0)) ) def ints(n: Int): Stream[Int] = Stream.cons(n, ints(n+1)) I think the Haskell solution is more compact due to syntactic sugar, curring and "parentheses-free-ness", *not* lazy evaluation. According to one guy's analogy: the Real World is strict - in order to drink tea, you have to put the cattle on the fire, wait until water boils, brew tea and then drink. Not the cattle is put on the fire, water boils and the tea is brewed when you take the empty cup to start drinking. :-) The question is the following: how big the gap between strict languages with lazy constructs and Haskell? Does the default lazyness have irrefutable advantage over default strictness? Thank you for the attention. With best regards, Nick.

12 23

ANNOUNCE: Derangement version 0.1.0
by dgriffi3＠uiuc.edu 20 Feb '07

20 Feb '07

This is the inital version of a very small library, mostly using the functional graph library, to find a derangement of a set, or rather a list. A derangement of a set is a permutation with no fixed points, like many constrained matching problems it is susceptible to solution via a Max-flow algorithm. The source and its darcs repository is available at http://www.acm.uiuc.edu/~dgriffi3/projects/derangement/ Of course questions, comments and patches are welcome. -- Dennis Griffith, ACM@UIUC Treasurer

1 0

Recursion in Haskell
by P. R. Stanley 20 Feb '07

20 Feb '07

Hi I understand the basic principle of recursion but have difficulty with the following: -- a recursive function -- for calculating the length of lists myLen [] = 0 myLen (x:xs) = 1 + myLen xs What's happening here? Top marks for a comprehensive jargon-free explanation. Thanks in advance Paul

9 15

Why do I have to specify (Monad m) here again?
by Marc Weber 19 Feb '07

19 Feb '07

Why do I have to specify (Monad m) here again? class (Monad m) => GetMV m a where ... instance GetMV m c where ... No instance for (Monad m) arising from the superclasses of an instance declaration possible fix: add (Monad m) to the instance declaration superclass context Marc

7 21

Lambada and connecting Haskell to a Weblogic server
by Joel Reymont 19 Feb '07

19 Feb '07

Folks, Where can I find Lambada these days and would it be of any use to me in trying to connect to a Weblogic server? To make the long story short, my broker's Java software connects to a remote Weblogic server and I would like to do the same. I suppose this would require me to implement Java RMI in Haskell which is non- trivial. I wonder if it would be easier for me to implement a Java server that talks to Weblogic and then connect to that server. What do you think? Thanks, Joel -- http://wagerlabs.com/

6 7