{-# LANGUAGE TypeFamilies #-}
{-# OPTIONS_GHC -fno-warn-unused-imports #-}
module Math.NumberTheory.Prefactored
( Prefactored(prefValue, prefFactors)
, fromValue
, fromFactors
) where
import Prelude hiding ((^), gcd)
import Control.Arrow
import Data.Euclidean
import Data.Semigroup
import Data.Semiring (Semiring(..), Mul(..), (^))
import qualified Data.Semiring as Semiring
import Unsafe.Coerce
import Math.NumberTheory.Euclidean.Coprimes
import Math.NumberTheory.Primes
import Math.NumberTheory.Primes.Types
data Prefactored a = Prefactored
{ forall a. Prefactored a -> a
prefValue :: a
, forall a. Prefactored a -> Coprimes a Word
prefFactors :: Coprimes a Word
} deriving (Prefactored a -> Prefactored a -> Bool
forall a. Eq a => Prefactored a -> Prefactored a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Prefactored a -> Prefactored a -> Bool
$c/= :: forall a. Eq a => Prefactored a -> Prefactored a -> Bool
== :: Prefactored a -> Prefactored a -> Bool
$c== :: forall a. Eq a => Prefactored a -> Prefactored a -> Bool
Eq, Int -> Prefactored a -> ShowS
forall a. Show a => Int -> Prefactored a -> ShowS
forall a. Show a => [Prefactored a] -> ShowS
forall a. Show a => Prefactored a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Prefactored a] -> ShowS
$cshowList :: forall a. Show a => [Prefactored a] -> ShowS
show :: Prefactored a -> String
$cshow :: forall a. Show a => Prefactored a -> String
showsPrec :: Int -> Prefactored a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Prefactored a -> ShowS
Show)
fromValue :: (Eq a, GcdDomain a) => a -> Prefactored a
fromValue :: forall a. (Eq a, GcdDomain a) => a -> Prefactored a
fromValue a
a = forall a. a -> Coprimes a Word -> Prefactored a
Prefactored a
a (forall a b.
(Eq a, GcdDomain a, Eq b, Num b) =>
a -> b -> Coprimes a b
singleton a
a Word
1)
fromFactors :: Semiring a => Coprimes a Word -> Prefactored a
fromFactors :: forall a. Semiring a => Coprimes a Word -> Prefactored a
fromFactors Coprimes a Word
as = forall a. a -> Coprimes a Word -> Prefactored a
Prefactored (forall a. Mul a -> a
getMul forall a b. (a -> b) -> a -> b
$ forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap (\(a
a, Word
k) -> forall a. a -> Mul a
Mul forall a b. (a -> b) -> a -> b
$ a
a forall a b. (Semiring a, Integral b) => a -> b -> a
^ Word
k) (forall a b. Coprimes a b -> [(a, b)]
unCoprimes Coprimes a Word
as)) Coprimes a Word
as
instance (Eq a, GcdDomain a) => Semiring (Prefactored a) where
Prefactored a
v1 Coprimes a Word
_ plus :: Prefactored a -> Prefactored a -> Prefactored a
`plus` Prefactored a
v2 Coprimes a Word
_
= forall a. (Eq a, GcdDomain a) => a -> Prefactored a
fromValue (a
v1 forall a. Semiring a => a -> a -> a
`plus` a
v2)
Prefactored a
v1 Coprimes a Word
f1 times :: Prefactored a -> Prefactored a -> Prefactored a
`times` Prefactored a
v2 Coprimes a Word
f2
= forall a. a -> Coprimes a Word -> Prefactored a
Prefactored (a
v1 forall a. Semiring a => a -> a -> a
`times` a
v2) (Coprimes a Word
f1 forall a. Semigroup a => a -> a -> a
<> Coprimes a Word
f2)
fromNatural :: Natural -> Prefactored a
fromNatural Natural
n = forall a. (Eq a, GcdDomain a) => a -> Prefactored a
fromValue (forall a. Semiring a => Natural -> a
fromNatural Natural
n)
instance (Eq a, Num a, GcdDomain a) => Num (Prefactored a) where
Prefactored a
v1 Coprimes a Word
_ + :: Prefactored a -> Prefactored a -> Prefactored a
+ Prefactored a
v2 Coprimes a Word
_
= forall a. (Eq a, GcdDomain a) => a -> Prefactored a
fromValue (a
v1 forall a. Num a => a -> a -> a
+ a
v2)
Prefactored a
v1 Coprimes a Word
_ - :: Prefactored a -> Prefactored a -> Prefactored a
- Prefactored a
v2 Coprimes a Word
_
= forall a. (Eq a, GcdDomain a) => a -> Prefactored a
fromValue (a
v1 forall a. Num a => a -> a -> a
- a
v2)
Prefactored a
v1 Coprimes a Word
f1 * :: Prefactored a -> Prefactored a -> Prefactored a
* Prefactored a
v2 Coprimes a Word
f2
= forall a. a -> Coprimes a Word -> Prefactored a
Prefactored (a
v1 forall a. Num a => a -> a -> a
* a
v2) (Coprimes a Word
f1 forall a. Semigroup a => a -> a -> a
<> Coprimes a Word
f2)
negate :: Prefactored a -> Prefactored a
negate (Prefactored a
v Coprimes a Word
f) = forall a. a -> Coprimes a Word -> Prefactored a
Prefactored (forall a. Num a => a -> a
negate a
v) Coprimes a Word
f
abs :: Prefactored a -> Prefactored a
abs (Prefactored a
v Coprimes a Word
f) = forall a. a -> Coprimes a Word -> Prefactored a
Prefactored (forall a. Num a => a -> a
abs a
v) Coprimes a Word
f
signum :: Prefactored a -> Prefactored a
signum (Prefactored a
v Coprimes a Word
_) = forall a. a -> Coprimes a Word -> Prefactored a
Prefactored (forall a. Num a => a -> a
signum a
v) forall a. Monoid a => a
mempty
fromInteger :: Integer -> Prefactored a
fromInteger Integer
n = forall a. (Eq a, GcdDomain a) => a -> Prefactored a
fromValue (forall a. Num a => Integer -> a
fromInteger Integer
n)
instance (Eq a, GcdDomain a, UniqueFactorisation a) => UniqueFactorisation (Prefactored a) where
factorise :: Prefactored a -> [(Prime (Prefactored a), Word)]
factorise (Prefactored a
_ Coprimes a Word
f)
= forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (\(a
x, Word
xm) -> forall a b. (a -> b) -> [a] -> [b]
map (\(Prime a
p, Word
k) -> (forall a. a -> Prime a
Prime forall a b. (a -> b) -> a -> b
$ forall a. (Eq a, GcdDomain a) => a -> Prefactored a
fromValue forall a b. (a -> b) -> a -> b
$ forall a. Prime a -> a
unPrime Prime a
p, Word
k forall a. Num a => a -> a -> a
* Word
xm)) (forall a. UniqueFactorisation a => a -> [(Prime a, Word)]
factorise a
x)) (forall a b. Coprimes a b -> [(a, b)]
unCoprimes Coprimes a Word
f)
isPrime :: Prefactored a -> Maybe (Prime (Prefactored a))
isPrime (Prefactored a
_ Coprimes a Word
f) = case forall a b. Coprimes a b -> [(a, b)]
unCoprimes Coprimes a Word
f of
[(a
n, Word
1)] -> forall a. a -> Prime a
Prime forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. (Eq a, GcdDomain a) => a -> Prefactored a
fromValue forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Prime a -> a
unPrime forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. UniqueFactorisation a => a -> Maybe (Prime a)
isPrime a
n
[(a, Word)]
_ -> forall a. Maybe a
Nothing