PrimeFactors.hs

{-
	Copyright (C) 2011 Dr. Alistair Ward

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program.  If not, see <http://www.gnu.org/licenses/>.
-}
{- |
 [@AUTHOR@]	Dr. Alistair Ward

 [@DESCRIPTION@]

	* Describes a list of /prime factors/.

	* The product of this list of prime-factors represents the /composite/ integer from which they were originally extracted.
-}

module Factory.Data.PrimeFactors(
-- * Types
-- ** Type-synonyms
	Factors,
-- * Functions
	insert',
--	invert,
	product',
	reduce,
--	reduceSorted,
--	sumExponents,
-- ** Operators
	(>*<),
	(>/<),
	(>^)
) where

import qualified	Control.Arrow
import			Control.Arrow((&&&))
import qualified	Data.List
import qualified	Data.Ord
import qualified	Factory.Math.DivideAndConquer	as Math.DivideAndConquer
import qualified	Factory.Data.Exponential	as Data.Exponential
import			Factory.Data.Exponential((<^), (=~))
import qualified	ToolShed.Data.List

infixl 7 >/<, >*<	-- Same as (/).
infixr 8 >^		-- Same as (^).

{- |
	* Each element of this list represents one /prime-factor/, expressed as an /exponential/ with a /prime/ base, of the original integer.

	* Whilst it only makes sense for both the /base/ and /exponent/ to be integral, these constrains are applied at the function-level as required.
-}
type Factors base exponent	= [Data.Exponential.Exponential base exponent]

{- |
	* Sorts a list representing a product of /prime factors/ by increasing /base/.

	* Multiplies 'Data.Exponential.Exponential's of similar /base/.
-}
reduce :: (Ord base, Num exponent, Ord exponent) => Factors base exponent -> Factors base exponent
reduce	= reduceSorted . Data.List.sort {-primarily by base-}

-- | Multiplies 'Data.Exponential.Exponential's of similar /base/.
reduceSorted :: (Eq base, Num exponent) => Factors base exponent -> Factors base exponent
-- reduceSorted	= map (Data.Exponential.getBase . head &&& sumExponents) . Data.List.groupBy (=~)	-- Slow
reduceSorted []	= []
reduceSorted (x : xs)
	| null matched	= x : reduceSorted remainder
	| otherwise	= Control.Arrow.second (+ sumExponents matched) x : reduceSorted remainder
	where
		(matched, remainder)	= span (=~ x) xs

{- |
	* Insert a 'Data.Exponential.Exponential', into a list representing a product of /prime factors/, multiplying with any incumbent of like /base/.

	* The list should be sorted by increasing /base/.

	* Preserves the sort-order.

	* CAVEAT: this is tolerably efficient for sporadic insertion; to insert a list, use '>*<'.
-}
insert' :: (Ord base, Num exponent) => Data.Exponential.Exponential base exponent -> Factors base exponent -> Factors base exponent
insert' e []		= [e]
insert' e l@(x : xs)	= case Data.Ord.comparing Data.Exponential.getBase e x of
	LT	-> e : l
	GT	-> x : insert' e xs	-- Recurse.
	_	-> Control.Arrow.second (+ Data.Exponential.getExponent e) x : xs	-- Multiply by adding exponents.

{- |
	* Multiplies two lists each representing a product of /prime factors/, and sorted by increasing /base/.

	* Preserves the sort-order.
-}
(>*<) :: (Ord base, Num exponent, Ord exponent) => Factors base exponent -> Factors base exponent -> Factors base exponent
l >*< r	= reduceSorted $ ToolShed.Data.List.merge l r

-- | Invert the product of a list /prime factors/, by negating each of the /exponents/.
invert :: Num exponent => Factors base exponent -> Factors base exponent
invert	= map Data.Exponential.invert

{- |
	* Divides two lists, each representing a product of /prime factors/, and sorted by increasing /base/.

	* Preserves the sort-order.
-}
(>/<) :: (Integral base, Integral exponent)
	=> Factors base exponent				-- ^ The list of /prime factors/ in the /numerator/.
	-> Factors base exponent				-- ^ The list of /prime factors/ in the /denominator/.
	-> (Factors base exponent, Factors base exponent)	-- ^ The ratio of /numerator/ and /denominator/, after like /prime factors/ are cancelled.
numerator >/< denominator	= filter (
	(> 0) . Data.Exponential.getExponent
 ) &&& invert . filter (
	(< 0) . Data.Exponential.getExponent
 ) $ numerator >*< invert denominator

{- |
	* Raise the product of a list /prime factors/ to the specified power.

	* CAVEAT: this merely involves raising each element to the specified power; cf. raising a /polynomial/ to a power.
-}
(>^) :: Num exponent => Factors base exponent -> exponent -> Factors base exponent
factors >^ power	= map (<^ power) factors

-- | Sum the /exponents/ of the specified list; as required to multiply exponentials with identical /base/.
sumExponents :: Num exponent => Factors base exponent -> exponent
sumExponents	= foldr ((+) . Data.Exponential.getExponent) 0

-- | Multiply a list of /prime factors/.
product' :: (Num base, Integral exponent)
	=> Math.DivideAndConquer.BisectionRatio
	-> Math.DivideAndConquer.MinLength
	-> Factors base exponent		-- ^ The list on which to operate.
	-> base					-- ^ The result.
product' bisectionRatio minLength	= Math.DivideAndConquer.product' bisectionRatio minLength . map Data.Exponential.evaluate