G'day all.
Thanks for your suggestions. Some comments...
Quoting Yitzchak Gale
o I think you are testing w' * w' < n each time, even when you are repeating factors of the same prime p. You only need to do that when you move to the next p
Good point, thanks.
o You can use divMod (or quotRem) instead of using div and then multiplying. (That's an ancient trick from C. It may not make a difference on modern CPUs.)
Yup, should have done that to begin with. At the very least, it's no worse than div-plus-multiplying.
o You are using the old functional programming trick of artificially creating state with extra function parameters. Nowadays we don't need that in Haskell - it is much simpler just to use the State monad.
That's true, but it does increase the number of dependencies, as noted in Simon Marlow's recent mail. The MTL might be deprecated soon, replaced by Iavor's library, for example. But your point is well taken. I probably would have done it that way
o I personally would much prefer a function that only returns prime numbers, not -1, 0, or 1.
Sounds like we actually need two functions: factor and primeFactors. (One is, of course, a trivial wrapper around the other.)
o I think that in most of the places where you fix the type as Int or Integer, you could leave it polymorphic and avoid a lot of coercing.
Possibly. I did have performance in mind while doing this. In particular: 1. Ints are usually cheaper than Integers, even when Integers are small enough to fit in an Int, because there's less boxing. In the case of the smallPrimes, for example, everything fits in an Int. Additionally, Ints can be unboxed later if appropriate. 2. Use memoing aggressively (if appropriate), but never use an unbounded amount of memory unless the client has a chance of controlling it. Your wheel implementation is a good example:
-- An infinite list of possible prime factors wheel :: Integral a => [a]
Looking at the type alone: - As it stands, this is not a CAF, and so has to be recomputed every time you use it. - If you did specialise it (perhaps via the SPECIALIZE pragma), it would be a CAF, but then you would need one copy for each specialisation, which (IMO) unnecessarily wastes memory. - Even if that wasn't a problem (say, you only had one specialisation), infinite list CAFs are bad for libraries because they cause space leaks which client code can't control. My original version of Prime had an infinite list CAF of primes, which I ditched in favour of primesUpTo for this very reason. (Well, that and it's faster because you don't need to sieve everything.) The moral of the story is that while I wouldn't think twice about using your solution as-is in a program (it's much more elegant than mine, IMO), in a general-purpose library, you have to tread a bit more carefully. I'll have a go at incorporating your changes. Thanks a lot. And, of course, anyone else with suggestions or patches are welcome to send them to me. Cheers, Andrew Bromage