-- |
-- Module:      Math.NumberTheory.Primes
-- Copyright:   (c) 2016-2018 Andrew.Lelechenko
-- Licence:     MIT
-- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
--

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE LambdaCase        #-}
{-# LANGUAGE PostfixOperators  #-}

{-# OPTIONS_GHC -fno-warn-orphans #-}

module Math.NumberTheory.Primes
    ( Prime
    , unPrime
    , toPrimeIntegral
    , nextPrime
    , precPrime
    , UniqueFactorisation(..)
    , factorBack
    , -- * Old interface
      primes
    ) where

import Data.Bits
import Data.Coerce
import Data.List.Infinite (Infinite(..), (...), (....))
import qualified Data.List.Infinite as Inf
import Data.Maybe
import Data.Word
import Numeric.Natural

import Math.NumberTheory.Primes.Counting (nthPrime, primeCount)
import qualified Math.NumberTheory.Primes.Factorisation.Montgomery as F (factorise)
import qualified Math.NumberTheory.Primes.Testing.Probabilistic as T (isPrime)
import Math.NumberTheory.Primes.Sieve.Eratosthenes (primes, sieveRange, primeList, psieveFrom, primeSieve)
import Math.NumberTheory.Primes.Small
import Math.NumberTheory.Primes.Types
import Math.NumberTheory.Utils (toWheel30, fromWheel30)
import Math.NumberTheory.Utils.FromIntegral

-- | A class for unique factorisation domains.
class Num a => UniqueFactorisation a where
  -- | Factorise a number into a product of prime powers.
  -- Factorisation of 0 is an undefined behaviour. Otherwise
  -- following invariants hold:
  --
  -- > abs n == abs (product (map (\(p, k) -> unPrime p ^ k) (factorise n)))
  -- > all ((> 0) . snd) (factorise n)
  --
  -- >>> factorise (1 :: Integer)
  -- []
  -- >>> factorise (-1 :: Integer)
  -- []
  -- >>> factorise (6 :: Integer)
  -- [(Prime 2,1),(Prime 3,1)]
  -- >>> factorise (-108 :: Integer)
  -- [(Prime 2,2),(Prime 3,3)]
  --
  -- This function is a replacement
  -- for 'Math.NumberTheory.Primes.Factorisation.factorise'.
  -- If you were looking for the latter, please import
  -- "Math.NumberTheory.Primes.Factorisation" instead of this module.
  --
  -- __Warning:__ there are no guarantees of any particular
  -- order of prime factors, do not expect them to be ascending. E. g.,
  --
  -- >>> factorise 10251562501
  -- [(Prime 101701,1),(Prime 100801,1)]
  factorise :: a -> [(Prime a, Word)]
  -- | Check whether an argument is prime.
  -- If it is then return an associated prime.
  --
  -- >>> isPrime (3 :: Integer)
  -- Just (Prime 3)
  -- >>> isPrime (4 :: Integer)
  -- Nothing
  -- >>> isPrime (-5 :: Integer)
  -- Just (Prime 5)
  --
  -- This function is a replacement
  -- for 'Math.NumberTheory.Primes.Testing.isPrime'.
  -- If you were looking for the latter, please import
  -- "Math.NumberTheory.Primes.Testing" instead of this module.
  isPrime   :: a -> Maybe (Prime a)

instance UniqueFactorisation Int where
  factorise :: Int -> [(Prime Int, Word)]
factorise = coerce :: forall a b. Coercible a b => a -> b
coerce forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Integral a => a -> [(a, Word)]
F.factorise
  isPrime :: Int -> Maybe (Prime Int)
isPrime Int
n = if Integer -> Bool
T.isPrime (forall a. Integral a => a -> Integer
toInteger Int
n) then forall a. a -> Maybe a
Just (forall a. a -> Prime a
Prime forall a b. (a -> b) -> a -> b
$ forall a. Num a => a -> a
abs Int
n) else forall a. Maybe a
Nothing

instance UniqueFactorisation Word where
  factorise :: Word -> [(Prime Word, Word)]
factorise = coerce :: forall a b. Coercible a b => a -> b
coerce forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Integral a => a -> [(a, Word)]
F.factorise
  isPrime :: Word -> Maybe (Prime Word)
isPrime Word
n = if Integer -> Bool
T.isPrime (forall a. Integral a => a -> Integer
toInteger Word
n) then forall a. a -> Maybe a
Just (forall a. a -> Prime a
Prime Word
n) else forall a. Maybe a
Nothing

instance UniqueFactorisation Integer where
  factorise :: Integer -> [(Prime Integer, Word)]
factorise = coerce :: forall a b. Coercible a b => a -> b
coerce forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Integral a => a -> [(a, Word)]
F.factorise
  isPrime :: Integer -> Maybe (Prime Integer)
isPrime Integer
n = if Integer -> Bool
T.isPrime Integer
n then forall a. a -> Maybe a
Just (forall a. a -> Prime a
Prime forall a b. (a -> b) -> a -> b
$ forall a. Num a => a -> a
abs Integer
n) else forall a. Maybe a
Nothing

instance UniqueFactorisation Natural where
  factorise :: Natural -> [(Prime Natural, Word)]
factorise = coerce :: forall a b. Coercible a b => a -> b
coerce forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Integral a => a -> [(a, Word)]
F.factorise
  isPrime :: Natural -> Maybe (Prime Natural)
isPrime Natural
n = if Integer -> Bool
T.isPrime (forall a. Integral a => a -> Integer
toInteger Natural
n) then forall a. a -> Maybe a
Just (forall a. a -> Prime a
Prime Natural
n) else forall a. Maybe a
Nothing

-- | Restore a number from its factorisation.
factorBack :: Num a => [(Prime a, Word)] -> a
factorBack :: forall a. Num a => [(Prime a, Word)] -> a
factorBack = forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map (\(Prime a
p, Word
k) -> forall a. Prime a -> a
unPrime Prime a
p forall a b. (Num a, Integral b) => a -> b -> a
^ Word
k)

-- | Smallest prime, greater or equal to argument.
--
-- > nextPrime (-100) ==    2
-- > nextPrime  1000  == 1009
-- > nextPrime  1009  == 1009
nextPrime :: (Bits a, Integral a, UniqueFactorisation a) => a -> Prime a
nextPrime :: forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
a -> Prime a
nextPrime a
n
  | a
n forall a. Ord a => a -> a -> Bool
<= a
2    = forall a. a -> Prime a
Prime a
2
  | a
n forall a. Ord a => a -> a -> Bool
<= a
3    = forall a. a -> Prime a
Prime a
3
  | a
n forall a. Ord a => a -> a -> Bool
<= a
5    = forall a. a -> Prime a
Prime a
5
  | Bool
otherwise = forall a. Infinite a -> a
Inf.head forall a b. (a -> b) -> a -> b
$ forall a b. (a -> Maybe b) -> Infinite a -> Infinite b
mapMaybeInf forall a. UniqueFactorisation a => a -> Maybe (Prime a)
isPrime forall a b. (a -> b) -> a -> b
$
                  forall a. (a -> Bool) -> Infinite a -> Infinite a
Inf.dropWhile (forall a. Ord a => a -> a -> Bool
< a
n) forall a b. (a -> b) -> a -> b
$ forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. (Num a, Bits a) => a -> a
fromWheel30 (forall a. (Integral a, Bits a) => a -> a
toWheel30 a
n ...)
                  -- dropWhile is important, because fromWheel30 (toWheel30 n) may appear to be < n.
                  -- E. g., fromWheel30 (toWheel30 94) == 97

-- | Largest prime, less or equal to argument. Undefined, when argument < 2.
--
-- > precPrime 100 == 97
-- > precPrime  97 == 97
precPrime :: (Bits a, Integral a, UniqueFactorisation a) => a -> Prime a
precPrime :: forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
a -> Prime a
precPrime a
n
  | a
n forall a. Ord a => a -> a -> Bool
< a
2     = forall a. HasCallStack => [Char] -> a
error [Char]
"precPrime: tried to take `precPrime` of an argument less than 2"
  | a
n forall a. Ord a => a -> a -> Bool
< a
3     = forall a. a -> Prime a
Prime a
2
  | a
n forall a. Ord a => a -> a -> Bool
< a
5     = forall a. a -> Prime a
Prime a
3
  | a
n forall a. Ord a => a -> a -> Bool
< a
7     = forall a. a -> Prime a
Prime a
5
  | Bool
otherwise = forall a. Infinite a -> a
Inf.head forall a b. (a -> b) -> a -> b
$ forall a b. (a -> Maybe b) -> Infinite a -> Infinite b
mapMaybeInf forall a. UniqueFactorisation a => a -> Maybe (Prime a)
isPrime forall a b. (a -> b) -> a -> b
$
                  forall a. (a -> Bool) -> Infinite a -> Infinite a
Inf.dropWhile (forall a. Ord a => a -> a -> Bool
> a
n) forall a b. (a -> b) -> a -> b
$ forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. (Num a, Bits a) => a -> a
fromWheel30 ((forall a. (Integral a, Bits a) => a -> a
toWheel30 a
n, forall a. (Integral a, Bits a) => a -> a
toWheel30 a
n forall a. Num a => a -> a -> a
- a
1) ....)
                  -- dropWhile is important, because fromWheel30 (toWheel30 n) may appear to be > n.
                  -- E. g., fromWheel30 (toWheel30 100) == 101

mapMaybeInf :: (a -> Maybe b) -> Infinite a -> Infinite b
mapMaybeInf :: forall a b. (a -> Maybe b) -> Infinite a -> Infinite b
mapMaybeInf = forall a b. (a -> b -> b) -> Infinite a -> b
Inf.foldr forall b c a. (b -> c) -> (a -> b) -> a -> c
. (forall b a. b -> (a -> b) -> Maybe a -> b
maybe forall a. a -> a
id forall a. a -> Infinite a -> Infinite a
(:<) .)

-------------------------------------------------------------------------------
-- Prime sequences

data Algorithm = IsPrime | Sieve

chooseAlgorithm :: Integral a => a -> a -> Algorithm
chooseAlgorithm :: forall a. Integral a => a -> a -> Algorithm
chooseAlgorithm a
from a
to
  | a
to forall a. Ord a => a -> a -> Bool
<= forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
sieveRange
  Bool -> Bool -> Bool
&& a
to forall a. Ord a => a -> a -> Bool
< a
from forall a. Num a => a -> a -> a
+ forall a b. (RealFrac a, Integral b) => a -> b
truncate (forall a. Floating a => a -> a
sqrt (forall a b. (Integral a, Num b) => a -> b
fromIntegral a
from) :: Double)
  = Algorithm
IsPrime
  | a
to forall a. Ord a => a -> a -> Bool
> forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
sieveRange
  Bool -> Bool -> Bool
&& a
to forall a. Ord a => a -> a -> Bool
< a
from forall a. Num a => a -> a -> a
+ forall a b. (RealFrac a, Integral b) => a -> b
truncate (Double
0.036 forall a. Num a => a -> a -> a
* forall a. Floating a => a -> a
sqrt (forall a b. (Integral a, Num b) => a -> b
fromIntegral a
from) forall a. Num a => a -> a -> a
+ Double
40000 :: Double)
  = Algorithm
IsPrime
  | Bool
otherwise
  = Algorithm
Sieve

succGeneric :: (Bits a, Integral a, UniqueFactorisation a) => Prime a -> Prime a
succGeneric :: forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a
succGeneric = \case
  Prime a
2 -> forall a. a -> Prime a
Prime a
3
  Prime a
3 -> forall a. a -> Prime a
Prime a
5
  Prime a
5 -> forall a. a -> Prime a
Prime a
7
  Prime a
p -> forall a. Infinite a -> a
Inf.head forall a b. (a -> b) -> a -> b
$ forall a b. (a -> Maybe b) -> Infinite a -> Infinite b
mapMaybeInf (forall a. UniqueFactorisation a => a -> Maybe (Prime a)
isPrime forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. (Num a, Bits a) => a -> a
fromWheel30) ((forall a. (Integral a, Bits a) => a -> a
toWheel30 a
p forall a. Num a => a -> a -> a
+ a
1) ...)

succGenericBounded
  :: (Bits a, Integral a, UniqueFactorisation a, Bounded a)
  => Prime a
  -> Prime a
succGenericBounded :: forall a.
(Bits a, Integral a, UniqueFactorisation a, Bounded a) =>
Prime a -> Prime a
succGenericBounded = \case
  Prime a
2 -> forall a. a -> Prime a
Prime a
3
  Prime a
3 -> forall a. a -> Prime a
Prime a
5
  Prime a
5 -> forall a. a -> Prime a
Prime a
7
  Prime a
p -> case forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe (forall a. UniqueFactorisation a => a -> Maybe (Prime a)
isPrime forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. (Num a, Bits a) => a -> a
fromWheel30) [forall a. (Integral a, Bits a) => a -> a
toWheel30 a
p forall a. Num a => a -> a -> a
+ a
1 .. forall a. (Integral a, Bits a) => a -> a
toWheel30 forall a. Bounded a => a
maxBound] of
    []    -> forall a. HasCallStack => [Char] -> a
error [Char]
"Enum.succ{Prime}: tried to take `succ' near `maxBound'"
    Prime a
q : [Prime a]
_ -> Prime a
q

predGeneric :: (Bits a, Integral a, UniqueFactorisation a) => Prime a -> Prime a
predGeneric :: forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a
predGeneric = \case
  Prime a
2 -> forall a. HasCallStack => [Char] -> a
error [Char]
"Enum.pred{Prime}: tried to take `pred' of 2"
  Prime a
3 -> forall a. a -> Prime a
Prime a
2
  Prime a
5 -> forall a. a -> Prime a
Prime a
3
  Prime a
7 -> forall a. a -> Prime a
Prime a
5
  Prime a
p -> forall a. Infinite a -> a
Inf.head forall a b. (a -> b) -> a -> b
$ forall a b. (a -> Maybe b) -> Infinite a -> Infinite b
mapMaybeInf (forall a. UniqueFactorisation a => a -> Maybe (Prime a)
isPrime forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. (Num a, Bits a) => a -> a
fromWheel30) ((forall a. (Integral a, Bits a) => a -> a
toWheel30 a
p forall a. Num a => a -> a -> a
- a
1, forall a. (Integral a, Bits a) => a -> a
toWheel30 a
p forall a. Num a => a -> a -> a
- a
2) ....)

-- 'dropWhile' is important, because 'psieveFrom' can actually contain primes less than p.
enumFromGeneric :: Integral a => Prime a -> [Prime a]
enumFromGeneric :: forall a. Integral a => Prime a -> [Prime a]
enumFromGeneric p :: Prime a
p@(Prime a
p')
  = coerce :: forall a b. Coercible a b => a -> b
coerce
  forall a b. (a -> b) -> a -> b
$ forall a. (a -> Bool) -> [a] -> [a]
dropWhile (forall a. Ord a => a -> a -> Bool
< Prime a
p)
  forall a b. (a -> b) -> a -> b
$ forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat
  forall a b. (a -> b) -> a -> b
$ forall a. (a -> Bool) -> [a] -> [a]
takeWhile (Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (t :: * -> *) a. Foldable t => t a -> Bool
null)
  forall a b. (a -> b) -> a -> b
$ forall a b. (a -> b) -> [a] -> [b]
map forall a. Integral a => PrimeSieve -> [Prime a]
primeList
  forall a b. (a -> b) -> a -> b
$ Integer -> [PrimeSieve]
psieveFrom
  forall a b. (a -> b) -> a -> b
$ forall a. Integral a => a -> Integer
toInteger a
p'

smallPrimesLimit :: Integral a => a
smallPrimesLimit :: forall a. Integral a => a
smallPrimesLimit = forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall a. Bounded a => a
maxBound :: Word16)

enumFromToGeneric :: (Bits a, Integral a, UniqueFactorisation a) => Prime a -> Prime a -> [Prime a]
enumFromToGeneric :: forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric p :: Prime a
p@(Prime a
p') q :: Prime a
q@(Prime a
q')
  | a
p' forall a. Ord a => a -> a -> Bool
<= forall a. Integral a => a
smallPrimesLimit, a
q' forall a. Ord a => a -> a -> Bool
<= forall a. Integral a => a
smallPrimesLimit
  = forall a b. (a -> b) -> [a] -> [b]
map (forall a. a -> Prime a
Prime forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (Integral a, Num b) => a -> b
fromIntegral) forall a b. (a -> b) -> a -> b
$ Word16 -> Word16 -> [Word16]
smallPrimesFromTo (forall a b. (Integral a, Num b) => a -> b
fromIntegral a
p') (forall a b. (Integral a, Num b) => a -> b
fromIntegral a
q')
  | a
p' forall a. Ord a => a -> a -> Bool
<= forall a. Integral a => a
smallPrimesLimit
  = forall a b. (a -> b) -> [a] -> [b]
map (forall a. a -> Prime a
Prime forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (Integral a, Num b) => a -> b
fromIntegral) (Word16 -> Word16 -> [Word16]
smallPrimesFromTo (forall a b. (Integral a, Num b) => a -> b
fromIntegral a
p') forall a. Integral a => a
smallPrimesLimit)
  forall a. [a] -> [a] -> [a]
++ forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric' (forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
a -> Prime a
nextPrime forall a. Integral a => a
smallPrimesLimit) Prime a
q
  | Bool
otherwise
  = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric' Prime a
p Prime a
q

enumFromToGeneric'
  :: (Bits a, Integral a, UniqueFactorisation a)
  => Prime a
  -> Prime a
  -> [Prime a]
enumFromToGeneric' :: forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric' p :: Prime a
p@(Prime a
p') q :: Prime a
q@(Prime a
q') = forall a. (a -> Bool) -> [a] -> [a]
takeWhile (forall a. Ord a => a -> a -> Bool
<= Prime a
q) forall a b. (a -> b) -> a -> b
$ forall a. (a -> Bool) -> [a] -> [a]
dropWhile (forall a. Ord a => a -> a -> Bool
< Prime a
p) forall a b. (a -> b) -> a -> b
$
  case forall a. Integral a => a -> a -> Algorithm
chooseAlgorithm a
p' a
q' of
    Algorithm
IsPrime -> forall a. a -> Prime a
Prime a
2 forall a. a -> [a] -> [a]
: forall a. a -> Prime a
Prime a
3 forall a. a -> [a] -> [a]
: forall a. a -> Prime a
Prime a
5 forall a. a -> [a] -> [a]
: forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe (forall a. UniqueFactorisation a => a -> Maybe (Prime a)
isPrime forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. (Num a, Bits a) => a -> a
fromWheel30) [forall a. (Integral a, Bits a) => a -> a
toWheel30 a
p' .. forall a. (Integral a, Bits a) => a -> a
toWheel30 a
q']
    Algorithm
Sieve   ->
      if a
q' forall a. Ord a => a -> a -> Bool
< forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
sieveRange
      then           forall a. Integral a => PrimeSieve -> [Prime a]
primeList forall a b. (a -> b) -> a -> b
$ Integer -> PrimeSieve
primeSieve forall a b. (a -> b) -> a -> b
$ forall a. Integral a => a -> Integer
toInteger a
q'
      else forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap forall a. Integral a => PrimeSieve -> [Prime a]
primeList forall a b. (a -> b) -> a -> b
$ Integer -> [PrimeSieve]
psieveFrom forall a b. (a -> b) -> a -> b
$ forall a. Integral a => a -> Integer
toInteger a
p'

enumFromThenGeneric :: (Bits a, Integral a, UniqueFactorisation a) => Prime a -> Prime a -> [Prime a]
enumFromThenGeneric :: forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromThenGeneric p :: Prime a
p@(Prime a
p') (Prime a
q') = case a
p' forall a. Ord a => a -> a -> Ordering
`compare` a
q' of
  Ordering
LT -> forall a. (a -> Bool) -> [a] -> [a]
filter (\(Prime a
r') -> (a
r' forall a. Num a => a -> a -> a
- a
p') forall a. Integral a => a -> a -> a
`rem` a
delta forall a. Eq a => a -> a -> Bool
== a
0) forall a b. (a -> b) -> a -> b
$ forall a. Integral a => Prime a -> [Prime a]
enumFromGeneric Prime a
p
    where
      delta :: a
delta = a
q' forall a. Num a => a -> a -> a
- a
p'
  Ordering
EQ -> forall a. a -> [a]
repeat Prime a
p
  Ordering
GT -> forall a. (a -> Bool) -> [a] -> [a]
filter (\(Prime a
r') -> (a
p' forall a. Num a => a -> a -> a
- a
r') forall a. Integral a => a -> a -> a
`rem` a
delta forall a. Eq a => a -> a -> Bool
== a
0) forall a b. (a -> b) -> a -> b
$ forall a. [a] -> [a]
reverse forall a b. (a -> b) -> a -> b
$ forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric (forall a. a -> Prime a
Prime a
2) Prime a
p
    where
      delta :: a
delta = a
p' forall a. Num a => a -> a -> a
- a
q'

enumFromThenToGeneric :: (Bits a, Integral a, UniqueFactorisation a) => Prime a -> Prime a -> Prime a -> [Prime a]
enumFromThenToGeneric :: forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> Prime a -> [Prime a]
enumFromThenToGeneric p :: Prime a
p@(Prime a
p') (Prime a
q') r :: Prime a
r@(Prime a
r') = case a
p' forall a. Ord a => a -> a -> Ordering
`compare` a
q' of
  Ordering
LT -> forall a. (a -> Bool) -> [a] -> [a]
filter (\(Prime a
t') -> (a
t' forall a. Num a => a -> a -> a
- a
p') forall a. Integral a => a -> a -> a
`rem` a
delta forall a. Eq a => a -> a -> Bool
== a
0) forall a b. (a -> b) -> a -> b
$ forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric Prime a
p Prime a
r
    where
      delta :: a
delta = a
q' forall a. Num a => a -> a -> a
- a
p'
  Ordering
EQ -> if a
p' forall a. Ord a => a -> a -> Bool
<= a
r' then forall a. a -> [a]
repeat Prime a
p else []
  Ordering
GT -> forall a. (a -> Bool) -> [a] -> [a]
filter (\(Prime a
t') -> (a
p' forall a. Num a => a -> a -> a
- a
t') forall a. Integral a => a -> a -> a
`rem` a
delta forall a. Eq a => a -> a -> Bool
== a
0) forall a b. (a -> b) -> a -> b
$ forall a. [a] -> [a]
reverse forall a b. (a -> b) -> a -> b
$ forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric Prime a
r Prime a
p
    where
      delta :: a
delta = a
p' forall a. Num a => a -> a -> a
- a
q'

instance Enum (Prime Integer) where
  toEnum :: Int -> Prime Integer
toEnum = Int -> Prime Integer
nthPrime
  fromEnum :: Prime Integer -> Int
fromEnum = Integer -> Int
integerToInt forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Integer
primeCount forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Prime a -> a
unPrime
  succ :: Prime Integer -> Prime Integer
succ = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a
succGeneric
  pred :: Prime Integer -> Prime Integer
pred = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a
predGeneric
  enumFrom :: Prime Integer -> [Prime Integer]
enumFrom = forall a. Integral a => Prime a -> [Prime a]
enumFromGeneric
  enumFromTo :: Prime Integer -> Prime Integer -> [Prime Integer]
enumFromTo = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric
  enumFromThen :: Prime Integer -> Prime Integer -> [Prime Integer]
enumFromThen = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromThenGeneric
  enumFromThenTo :: Prime Integer -> Prime Integer -> Prime Integer -> [Prime Integer]
enumFromThenTo = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> Prime a -> [Prime a]
enumFromThenToGeneric

instance Enum (Prime Natural) where
  toEnum :: Int -> Prime Natural
toEnum = forall a. a -> Prime a
Prime forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Natural
integerToNatural forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Prime a -> a
unPrime forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Prime Integer
nthPrime
  fromEnum :: Prime Natural -> Int
fromEnum = Integer -> Int
integerToInt forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Integer
primeCount forall b c a. (b -> c) -> (a -> b) -> a -> c
. Natural -> Integer
naturalToInteger forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Prime a -> a
unPrime
  succ :: Prime Natural -> Prime Natural
succ = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a
succGeneric
  pred :: Prime Natural -> Prime Natural
pred = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a
predGeneric
  enumFrom :: Prime Natural -> [Prime Natural]
enumFrom = forall a. Integral a => Prime a -> [Prime a]
enumFromGeneric
  enumFromTo :: Prime Natural -> Prime Natural -> [Prime Natural]
enumFromTo = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric
  enumFromThen :: Prime Natural -> Prime Natural -> [Prime Natural]
enumFromThen = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromThenGeneric
  enumFromThenTo :: Prime Natural -> Prime Natural -> Prime Natural -> [Prime Natural]
enumFromThenTo = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> Prime a -> [Prime a]
enumFromThenToGeneric

instance Enum (Prime Int) where
  toEnum :: Int -> Prime Int
toEnum Int
n = if Integer
p forall a. Ord a => a -> a -> Bool
> Int -> Integer
intToInteger forall a. Bounded a => a
maxBound
    then forall a. HasCallStack => [Char] -> a
error forall a b. (a -> b) -> a -> b
$ [Char]
"Enum.toEnum{Prime}: " forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> [Char]
show Int
n forall a. [a] -> [a] -> [a]
++ [Char]
"th prime = " forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> [Char]
show Integer
p forall a. [a] -> [a] -> [a]
++ [Char]
" is out of bounds of Int"
    else forall a. a -> Prime a
Prime (Integer -> Int
integerToInt Integer
p)
    where
      Prime Integer
p = Int -> Prime Integer
nthPrime Int
n
  fromEnum :: Prime Int -> Int
fromEnum = Integer -> Int
integerToInt forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Integer
primeCount forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Integer
intToInteger forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Prime a -> a
unPrime
  succ :: Prime Int -> Prime Int
succ = forall a.
(Bits a, Integral a, UniqueFactorisation a, Bounded a) =>
Prime a -> Prime a
succGenericBounded
  pred :: Prime Int -> Prime Int
pred = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a
predGeneric
  enumFrom :: Prime Int -> [Prime Int]
enumFrom = forall a. Integral a => Prime a -> [Prime a]
enumFromGeneric
  enumFromTo :: Prime Int -> Prime Int -> [Prime Int]
enumFromTo = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric
  enumFromThen :: Prime Int -> Prime Int -> [Prime Int]
enumFromThen = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromThenGeneric
  enumFromThenTo :: Prime Int -> Prime Int -> Prime Int -> [Prime Int]
enumFromThenTo = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> Prime a -> [Prime a]
enumFromThenToGeneric

instance Bounded (Prime Int) where
  minBound :: Prime Int
minBound = forall a. a -> Prime a
Prime Int
2
  maxBound :: Prime Int
maxBound = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
a -> Prime a
precPrime forall a. Bounded a => a
maxBound

instance Enum (Prime Word) where
  toEnum :: Int -> Prime Word
toEnum Int
n = if Integer
p forall a. Ord a => a -> a -> Bool
> Word -> Integer
wordToInteger forall a. Bounded a => a
maxBound
    then forall a. HasCallStack => [Char] -> a
error forall a b. (a -> b) -> a -> b
$ [Char]
"Enum.toEnum{Prime}: " forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> [Char]
show Int
n forall a. [a] -> [a] -> [a]
++ [Char]
"th prime = " forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> [Char]
show Integer
p forall a. [a] -> [a] -> [a]
++ [Char]
" is out of bounds of Word"
    else forall a. a -> Prime a
Prime (Integer -> Word
integerToWord Integer
p)
    where
      Prime Integer
p = Int -> Prime Integer
nthPrime Int
n
  fromEnum :: Prime Word -> Int
fromEnum = Integer -> Int
integerToInt forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Integer
primeCount forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word -> Integer
wordToInteger forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Prime a -> a
unPrime
  succ :: Prime Word -> Prime Word
succ = forall a.
(Bits a, Integral a, UniqueFactorisation a, Bounded a) =>
Prime a -> Prime a
succGenericBounded
  pred :: Prime Word -> Prime Word
pred = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a
predGeneric
  enumFrom :: Prime Word -> [Prime Word]
enumFrom = forall a. Integral a => Prime a -> [Prime a]
enumFromGeneric
  enumFromTo :: Prime Word -> Prime Word -> [Prime Word]
enumFromTo = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromToGeneric
  enumFromThen :: Prime Word -> Prime Word -> [Prime Word]
enumFromThen = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> [Prime a]
enumFromThenGeneric
  enumFromThenTo :: Prime Word -> Prime Word -> Prime Word -> [Prime Word]
enumFromThenTo = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
Prime a -> Prime a -> Prime a -> [Prime a]
enumFromThenToGeneric

instance Bounded (Prime Word) where
  minBound :: Prime Word
minBound = forall a. a -> Prime a
Prime Word
2
  maxBound :: Prime Word
maxBound = forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
a -> Prime a
precPrime forall a. Bounded a => a
maxBound