
Daniel Fischer <daniel.is.fischer <at> web.de> writes:
>
>
> The below code is now a wellbehaved memory citizen (3MB for the 100
millionth prime, about the same as the PQ code). It still is considerably
slower than the PQ code.
> In terms of MUT times as reported by +RTS sstderr  as well as (MUT+GC)
times  (measured once for prime No. 5*10^5, 10^6, 2*10^6, 4*10^6, 10^7 to get
a rough tendency), it seems to scale a wee bit better than any of the other
tfold versions I created, but a little worse than the PQ versions.
> The relation of MUT times isn't too bad, but the GC times are rather abysmal
(3040%).
>
> 
> data People a = P { vips :: [a], dorks :: [a] }
>
> celebrate :: a > People a > People a
> celebrate x p = P (x:vips p) (dorks p)
>
> primes :: forall a. Integral a => () > [a]
> primes () = 2:3:5:7:11:13:primes'
> ÂÂ where
> ÂÂÂ primes' = roll 17 wheel13 `minus` compos primes'''
primes'' = 17:19:23:29:31:rollFrom 37 `minus` compos primes''
> primes''' = 17:19:23:29:31:37:rollFrom 41 `minus` compos primes''
>
> pmults :: a > People a
> pmults p = case map (*p) (rollFrom p) of
> (x:xs) > P [x] xs
>
> multip :: [a] > [People a]
> multip ps = map pmults ps
>
> compos :: [a] > [a]
compos = vips . smartfold mergeSP . multip
>
>
> smartfold f = tfold f . pairwise f
>
> tfold f (a:b:c:xs) = (a `f` (b `f` c)) `f` smartfold f xs
>
> pairwise f (x:y:ys)Â = f x y : pairwise f ys
>
> mergeSP :: Integral a => People a > People a > People a
> mergeSP [email protected](P a _) p2 = P (a ++ vips mrgd) (dorks mrgd)
> where
> mrgd = spMerge (dorks p1) (vips p2) (dorks p2)
> spMerge l1 [] l3 = P [] (merge l1 l3)
> spMerge [email protected](x:xs) [email protected](y:ys) l3 = case compare x y of
> LT > celebrate x (spMerge xs l2 l3)
> EQ > celebrate x (spMerge xs ys l3)
> GT > celebrate y (spMerge l1 ys l3)
>
> 
>
Hi Daniel,
Is it so that you went back to my fold structure? Was it better for really big
numbers of primes?
I had the following for ages (well, at least two weeks) but I thought it was
slower and took more memory (that was _before_ the 'noshare' and 'feeder'
stuff). I can see the only difference in that you've rewritten spMerge in a
tailrecursive style with explicitly deconstructed parts; mine was relying on
the compiler (8L) to decouple the two pipes and recognize that the second
just passes along the final result, unchanged.
The two versions seem to me to be _exactly_ operationally equivalent. All this
searching for the code better understood by the compiler is _*very*_
frustrating, as it doesn't reflect on the semantics of the code, or even the
operational semantics of the code. :[
Weren't the P's supposed to disappear completely in the compiled code? Aren't
types just a _behavioral_ definitions??? Aren't we supposed to be able to
substitute equals for equals dammit??
Is this the state of our _best_ Haskell compiler????
module Primes8 where
import Data.Monoid
data (Ord a) => SplitList a = P [a] [a]
instance (Ord a) => Monoid (SplitList a) where
mempty = P [] []
 {x  x::SplitList a} form a monoid under mappend
mappend (P a b) ~(P c d) = let P bc b' = spMerge b c
in P (a ++ bc) (merge b' d)
where
spMerge :: (Ord a) => [a] > [a] > SplitList a
spMerge [email protected](x:xs) [email protected](y:ys) = case compare x y of
LT > P (x:c) d where (P c d) = spMerge xs w
EQ > P (x:c) d where (P c d) = spMerge xs ys
GT > P (y:c) d where (P c d) = spMerge u ys
spMerge u [] = P [] u
spMerge [] w = P [] w
mconcat ms = fold mappend (pairwise mappend ms)
where
fold f (a: ~(b: ~(c:xs)))
= (a `f` (b `f` c)) `f` fold f (pairwise f xs)
pairwise f (x:y:ys) = f x y:pairwise f ys
primes :: Integral a => () > [a]
primes () = 2:3:5:7:primes'
where
primes' = [11,13] ++ drop 2 (rollFrom 11) `minus` comps
mults = map (\p> P [p*p] [p*n  n< tail $ rollFrom p]) $ primes'
P comps _ = mconcat mults
_______________________________________________
HaskellCafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskellcafe

