{-
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 .
-}
{- |
[@AUTHOR@] Dr. Alistair Ward
[@DESCRIPTION@]
* Provides a polymorphic algorithm, to /unfold/ a list into a tree, to which an /associative binary operator/ is then applied to re-/fold/ the tree to a /scalar/.
* Implementations of this strategy have been provided for /addition/ and /multiplication/,
though other associative binary operators, like 'gcd' or 'lcm' could also be used.
* Where the contents of the list are consecutive, a more efficient implementation is available in /Factory.Data.Interval/.
-}
module Factory.Math.DivideAndConquer(
-- * Types
-- ** Type-synonyms
BisectionRatio,
MinLength,
-- * Functions
divideAndConquer,
product',
sum'
) where
import Control.Arrow((***))
import qualified Control.Parallel.Strategies
import qualified Data.Monoid
import qualified Data.Ratio
{- |
* The ratio of the original list-length at which to bisect.
* CAVEAT: the value can overflow.
-}
type BisectionRatio = Data.Ratio.Ratio Int
-- | The list-length beneath which to terminate bisection.
type MinLength = Int
{- |
* Reduces a list to a single scalar encapsulated in a 'Data.Monoid.Monoid',
using a /divide-and-conquer/ strategy,
bisecting the list and recursively evaluating each part; .
* By choosing a 'bisectionRatio' other than @(1 % 2)@, the bisection can be made asymmetrical.
The specified ratio represents the length of the left-hand portion, over the original list-length;
eg. @(1 % 3)@ results in the first part, half the length of the second.
* This process of recursive bisection, is terminated beneath the specified minimum list-length,
after which the /monoid/'s binary operator is directly /folded/ over the list.
* One can view this as a ,
in which the list is exploded into a binary tree-structure
(each leaf of which contains a list of up to 'minLength' integers, and each node of which contains an associative binary operator),
and then collapsed to a scalar, by application of the operators.
-}
divideAndConquer :: Data.Monoid.Monoid monoid
=> BisectionRatio -- ^ The ratio of the original list-length at which to bisect.
-> MinLength -- ^ For efficiency, the list will not be bisected, when it's length has been reduced to this value.
-> [monoid] -- ^ The list on which to operate.
-> monoid -- ^ The resulting scalar.
divideAndConquer bisectionRatio minLength l
| any ($ apportion minLength) [
(< 1), -- The left-hand list may be null.
(> pred minLength) -- The right-hand list may be null.
] = error $ "Factory.Math.DivideAndConquer.divideAndConquer:\tbisectionRatio='" ++ show bisectionRatio ++ "' is incompatible with minLength=" ++ show minLength ++ "."
| otherwise = slave (length l) l
where
apportion :: Int -> Int
apportion list = (list * Data.Ratio.numerator bisectionRatio) `div` Data.Ratio.denominator bisectionRatio
slave len list
| len <= minLength = Data.Monoid.mconcat list -- Fold the monoid's binary operator over the list.
| otherwise = uncurry Data.Monoid.mappend . Control.Parallel.Strategies.withStrategy (
Control.Parallel.Strategies.parTuple2 Control.Parallel.Strategies.rseq Control.Parallel.Strategies.rseq
) . (slave cut *** slave (len - cut)) $ splitAt cut list where -- Apply the monoid's binary operator to the two operands resulting from bisection.
cut = apportion len
{- |
* Multiplies the specified list of numbers.
* Since the result can be large, 'divideAndConquer' is used in an attempt to form operands of a similar order of magnitude,
which creates scope for the use of more efficient multiplication-algorithms.
-}
product' :: Num n
=> BisectionRatio -- ^ The ratio of the original list-length at which to bisect.
-> MinLength -- ^ For efficiency, the list will not be bisected, when it's length has been reduced to this value.
-> [n] -- ^ The numbers whose product is required.
-> n -- ^ The resulting product.
product' bisectionRatio minLength = Data.Monoid.getProduct . divideAndConquer bisectionRatio minLength . map Data.Monoid.Product
{- |
* Sums the specified list of numbers.
* Since the result can be large, 'divideAndConquer' is used in an attempt to form operands of a similar order of magnitude,
which creates scope for the use of more efficient multiplication-algorithms.
/Multiplication/ is required for the /addition/ of 'Rational' numbers by cross-multiplication;
this function is unlikely to be useful for other numbers.
-}
sum' :: Num n
=> BisectionRatio -- ^ The ratio of the original list-length at which to bisect.
-> MinLength -- ^ For efficiency, the list will not be bisected, when it's length has been reduced to this value.
-> [n] -- ^ The numbers whose sum is required.
-> n -- ^ The resulting sum.
sum' bisectionRatio minLength = Data.Monoid.getSum . divideAndConquer bisectionRatio minLength . map Data.Monoid.Sum