[Haskell-cafe] Re: FASTER primes

Daniel Fischer daniel.is.fischer at web.de
Mon Jan 4 20:43:42 EST 2010


Am Montag 04 Januar 2010 22:25:28 schrieb Daniel Fischer:
> compos ps = fst (tfold mergeSP $ nwise 1 mergeSP (pairwise mergeSP (multip
> ps)))
>
> tfold f (a: ~(b: ~(c:xs)))
>                      = (a `f` (b `f` c)) `f` tfold f xs
>
> nwise k f xs = let (ys,zs) = splitAt k xs in rfold f ys : nwise (k+1) f zs
>
> rfold f [x] = x
> rfold f (x:xs) = x `f` rfold f xs
>
> memory still grows, but much slower, in my tests, due to the much smaller
> GC time, it's a bit faster than the version with the original tfold.

Not for larger inputs (but not so large that the tree-fold dies OOM).
Fix rfold:

rfold f [x] = x
rfold f xs = rfold f (pairwise f xs)

and it's faster also for those.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100104/a8bb9b45/attachment-0001.html


More information about the Haskell-Cafe mailing list