4 ms·
I don't understand why they want to use this code primes = sieve [2..] where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0] As their fir
by thomasahle 12y ago
I don't understand why they want to use this code
primes = sieve [2..]
where sieve (p:xs) =
p : sieve [x | x <- xs, x `mod` p /= 0]
As their first example of Haskell. It's a prime generator based on trial division. And not even trial division up to sqrt of the number you test, but all the way up.
I like the idea of a small snippet showing of the power of haskell, but there are many much better examples imho. Perhaps the website could just choose one at random at each load?
- pervycreeper 12y agoIf the point is to show the power and elegance of the language, why would they complicate the expression with optimizations? The sqrt example is obvious to anyone who understands that line anyway.
- dkersten 12y agoWhat is the point of demonstrating the power an elegance with an example that will (hopefully!) never appear in any real world code? Better to show how the language is still powerful and elegant when taking into account the edge cases and common optimizations. Writing elegant non-real-world code is much easier (in any language!) than writing real code.
- sigilion 12y agoIt's the Sieve of Eratosthenes, which is a fairly classic algorithm.
- Moyamo 12y agoNo it's not. It is only superficially[1]. The sieve of Eratosthenes goes like this: 1) Mark 2 as prime. Let it be n. 2) Mark all numbers of the form i times n as composite, where i is a positive integer. (We can do this by stepping over multiples of n. No multiplication needs to take place. 3) The next unmarked number is prime. Let it be n. Goto 2 Notice how this alogorithm does not use division. Division in modern CPUs is slow. The algorithm presented uses the `mod` operator, which does division. This algorithm is equivalent to the Trial Division Algorithm. Instead of "deleting" multiples of n as composite, this algorithm tests all numbers greater than n for divisibilty by n, and then only does it "delete" the number. For a more detailed explanation, see http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf [1] https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Trial_division https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Trial_di...
- deleted 12y ago[deleted]