Daniel Fischer
Am Donnerstag 07 Januar 2010 11:43:44 schrieb Heinrich Apfelmus:
Will Ness wrote:
Hm? In my world view, there is only reduction to normal form and I don't see how "allocate its own storage" fits in there. Okasaki having shown something to that end would be new to me?
Perhaps what was meant was "storage must be allocated for each filter" (which, however, seems trivial).
I still contend that in case of nested filters, where each filter has only one consumer, even that isn't ultimately necessary (a chain of pointers could be formed). That's because there's no "peek"s, only "pull"s there. If the filters are used in merge situation, then there will be some "peek"s so current value must be somehow stored, though it's better to be made explicit and thus static (the place for it, I mean, instead of the "rolling" cons cell). Such implementation technique would prevent some extra gc.
Then under merging these split pairs form a monoid, so can be rearranged in a tree. If you haven't seen it yet, it uses a different folding structure to your code, with a lower total cost of multiples production (estimated as Sum (1/p)*depth):
correction:
tfold f (x:y:z:xs) = (x `f` (y `f` z)) `f` tfold f (pairwise f xs) comps = tfold mergeSP $ pairwise mergeSP multips
The idea being that each prime produces 1/p composites each "turn" and it takes time depth to trickle it to the top? Sounds reasonable, but remember that a prime p does not start to generate composites until the "turn count" has reached p^2, so it might occupy a place of low depth in the tree that is better spent on the previous primes.
That might be why Daniel's structure is better: it plunges down faster than mine. "treefold" structure was: (2+4) + ( (4+8) + ( (8+16) + ( (16+32) + ( (32+64) + ....... )))) dpths: 3 4 4 5 5 6 6 7 7 8 daniel's: (2+(4+6)) + ( (8+(10+12)) + ( (14+(16+18)) + ( (20+(22+24)) + .... )) 3 5 5.4 6 7.8 7.9 8 9 9.5 9.6 10.7 10.8
primes () = 2:3:5:7:11:13:primes' where primes' = roll 17 wheel13 `minus` compos primes''' primes'' = 17:19:23:29:31:37:rollFrom 41 `minus` compos primes'' primes''' = 17:19:23:29:31:37:rollFrom 41 `minus` compos primes''
Haven't read through the whole thing yet. :) :) I thought there was a typo there. There isn't. BTW using the no-share switch isn't necessary if we just write it down twice with some variations, like primes''' = let (h,t)=span (< 17^2) roll 17 wheel13 in h++t `minus` compos primes'' As we've found out, compilers aren't _that_ smart yet.