Newtype for primes

[Bodigrim]

This is a big breaking change, introducing (after all this time) a newtype for primes.

Remove 'Prime' type family and introduce 'Prime' newtype

Two years ago I designed a 'Prime' type family:

type family Prime (f :: *) :: *

newtype Prm = Prm Word
type instance Prime Int  = Prm
type instance Prime Word = Prm

newtype Prime = Prime Natural
type instance Prime Integer = PrimeNat
type instance Prime Natural = PrimeNat

unPrime :: Prime a -> a

The idea was that a type for primes should contain only such prime elements p for which abs p == p, and this invariant must be forced by construction. It appeared that this approach has serious drawbacks.

1. It is difficult to design Prime a for other unique factorisation domains. For example, even if we define data GaussianPrime = GaussianPrime Natural Natural (which is not very convenient), it still contains both associated primes GaussianPrime 3 0 and GaussianPrimes 0 3. And things become even worse for EisensteinInteger.

2. Conversion from Prime Integer to Integer is not free. (Conversion from Prime Int to Int is almost free.)

3. Since the type family is not injective you need a type annotation each time you use unPrime. For instance, GHC cannot determine which is the type of unPrime (Prime 1). Is it Natural or Integer?

That said, I decided to switch from a type family to a newtype:

newtype Prime a = Prime { unPrime :: a }

Since Prime is used in UniqueFactorisation type class, it underwent breaking transformation as well.

Use 'Prime' newtype in user-facing functions

I decided do not re-export Math.NumberTheory.Primes.{Factorisation,Testing} from Math.NumberTheory.Primes, but expose Prime- and UniqueFactorisation-based interface instead. My intention is to show best and up-to-date practices first and hide an outdated low-level interface, which often confuses users.

Sieve functions changed they output from a to Prime a:

primes :: Integral a => [Prime a]
primeList :: forall a. Integral a => PrimeSieve -> [Prime a]
sieveFrom :: Integer -> [Prime Integer]

I expect this to be a major breakage, but I see no way to sweeten it.

Also nthPrime changed it return type and outputs Prime Integer now.

@b-mehta @rockbmb what is your opinion?

[b-mehta]

I like this idea a lot, although it seems like the Prime constructor is being exported - unless I'm missing something. Is this a good idea?

[Bodigrim]

It is exported from Math.NumberTheory.Primes.Types, because we create primes in many different modules. But it is not accessible for end user, because Math.NumberTheory.Primes.Types is not an exposed module.

[rockbmb]

I'll take a look at this next weekend.

[rockbmb]

@Bodigrim related to but not contained by this PR, there's another issue I wanted to fix as well which is user-facing modules. For example, all of these modules:

Math.NumberTheory.ArithmeticFunctions
Math.NumberTheory.ArithmeticFunctions.Class
Math.NumberTheory.ArithmeticFunctions.Mertens
Math.NumberTheory.ArithmeticFunctions.Moebius
Math.NumberTheory.ArithmeticFunctions.SieveBlock
Math.NumberTheory.ArithmeticFunctions.Standard

(seen from 0.7.0.0, the latest version)

are exported by the package, when either

Math.NumberTheory.ArithmeticFunctions

or

Math.NumberTheory.ArithmeticFunctions.Class
Math.NumberTheory.ArithmeticFunctions.Mertens
Math.NumberTheory.ArithmeticFunctions.Moebius
Math.NumberTheory.ArithmeticFunctions.SieveBlock
Math.NumberTheory.ArithmeticFunctions.Standard

should be exported. In my opinion, at least. There's no use in having a reexporting module if the reexported modules are exported by themselves too.

[b-mehta]

@Bodigrim, makes sense, thanks! I'll take a closer look before next week.

[Bodigrim]

There's no use in having a reexporting module if the reexported modules are exported by themselves too.

I am not convinced that this is necessarily true in general. It may be convenient in some cases. But following your suggestion I've hidden Math.NumberTheory.ArithmeticFunctions.{Class,Standard} (which are reexported in full from Math.NumberTheory.ArithmeticFunctions) to other-modules in https://github.com/cartazio/arithmoi/commit/08f3f1472e2430ef85e4e14b85b46d8371ce19ea.

[rockbmb]

I agree with the general idea of the PR, and I've taken a look at all the changes (not at once).

Have you run all benchmarks from before and after the modifications to see if there's any significant change?

[Bodigrim]

I run benchmarks, they look good.