Prime numbers miscellaneous
From HaskellWiki
(Difference between revisions)
(page created; moving here some leftovers from Prime_numbers page) |
(→Implicit Heap) |
||
| Line 4: | Line 4: | ||
The following is an original implicit heap implementation for the sieve of | The following is an original implicit heap implementation for the sieve of | ||
| - | Eratosthenes, kept here for historical record. The [[Prime_numbers#Tree Merging with Wheel]] section | + | Eratosthenes, kept here for historical record. The [[Prime_numbers#Tree Merging with Wheel]] section simplifies it, removing the <code>People a</code> structure altogether, and improves upon it by using a folding tree structure better adjusted for primes processing, and a [[Prime_numbers#Euler.27s_Sieve | wheel]] optimization. |
See also the message threads [http://thread.gmane.org/gmane.comp.lang.haskell.cafe/25270/focus=25312 Re: "no-coding" functional data structures via lazyness] for more about how merging ordered lists amounts to creating an implicit heap and [http://thread.gmane.org/gmane.comp.lang.haskell.cafe/26426/focus=26493 Re: Code and Perf. Data for Prime Finders] for an explanation of the <code>People a</code> structure that makes it work. | See also the message threads [http://thread.gmane.org/gmane.comp.lang.haskell.cafe/25270/focus=25312 Re: "no-coding" functional data structures via lazyness] for more about how merging ordered lists amounts to creating an implicit heap and [http://thread.gmane.org/gmane.comp.lang.haskell.cafe/26426/focus=26493 Re: Code and Perf. Data for Prime Finders] for an explanation of the <code>People a</code> structure that makes it work. | ||
Revision as of 06:26, 7 June 2011
For a context to this, please see Prime numbers.
Implicit Heap
The following is an original implicit heap implementation for the sieve of
Eratosthenes, kept here for historical record. The Prime_numbers#Tree Merging with Wheel section simplifies it, removing the People a structure altogether, and improves upon it by using a folding tree structure better adjusted for primes processing, and a wheel optimization.
See also the message threads Re: "no-coding" functional data structures via lazyness for more about how merging ordered lists amounts to creating an implicit heap and Re: Code and Perf. Data for Prime Finders for an explanation of the People a structure that makes it work.
data People a = VIP a (People a) | Crowd [a] mergeP :: Ord a => People a -> People a -> People a mergeP (VIP x xt) ys = VIP x $ mergeP xt ys mergeP (Crowd xs) (Crowd ys) = Crowd $ merge xs ys mergeP xs@(Crowd (x:xt)) ys@(VIP y yt) = case compare x y of LT -> VIP x $ mergeP (Crowd xt) ys EQ -> VIP x $ mergeP (Crowd xt) yt GT -> VIP y $ mergeP xs yt merge :: Ord a => [a] -> [a] -> [a] merge xs@(x:xt) ys@(y:yt) = case compare x y of LT -> x : merge xt ys EQ -> x : merge xt yt GT -> y : merge xs yt diff xs@(x:xt) ys@(y:yt) = case compare x y of LT -> x : diff xt ys EQ -> diff xt yt GT -> diff xs yt foldTree :: (a -> a -> a) -> [a] -> a foldTree f ~(x:xs) = x `f` foldTree f (pairs xs) where pairs ~(x: ~(y:ys)) = f x y : pairs ys primes, nonprimes :: [Integer] primes = 2:3:diff [5,7..] nonprimes nonprimes = serve . foldTree mergeP . map multiples $ tail primes where multiples p = vip [p*p,p*p+2*p..] vip (x:xs) = VIP x $ Crowd xs serve (VIP x xs) = x:serve xs serve (Crowd xs) = xs
nonprimes effectively implements a heap, exploiting lazy evaluation.
