[Haskell-cafe] NumberTheory library

[ajb at spamcop.net]

G'day all.

Thanks for your suggestions.  Some comments...

Quoting Yitzchak Gale <gale at sefer.org>:

> 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