Personal tools

Prime numbers miscellaneous

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(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 above 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.
+
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.