module Factory.Math.DivideAndConquer(
BisectionRatio,
MinLength,
divideAndConquer,
product',
sum'
) where
import Control.Arrow((***))
import qualified Control.Parallel.Strategies
import qualified Data.Monoid
import qualified Data.Ratio
type BisectionRatio = Data.Ratio.Ratio Int
type MinLength = Int
divideAndConquer :: Data.Monoid.Monoid monoid
=> BisectionRatio
-> MinLength
-> [monoid]
-> monoid
divideAndConquer :: BisectionRatio -> MinLength -> [monoid] -> monoid
divideAndConquer BisectionRatio
bisectionRatio MinLength
minLength [monoid]
l
| ((MinLength -> Bool) -> Bool) -> [MinLength -> Bool] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any ((MinLength -> Bool) -> MinLength -> Bool
forall a b. (a -> b) -> a -> b
$ MinLength -> MinLength
apportion MinLength
minLength) [
(MinLength -> MinLength -> Bool
forall a. Ord a => a -> a -> Bool
< MinLength
1),
(MinLength -> MinLength -> Bool
forall a. Ord a => a -> a -> Bool
> MinLength -> MinLength
forall a. Enum a => a -> a
pred MinLength
minLength)
] = [Char] -> monoid
forall a. HasCallStack => [Char] -> a
error ([Char] -> monoid) -> [Char] -> monoid
forall a b. (a -> b) -> a -> b
$ [Char]
"Factory.Math.DivideAndConquer.divideAndConquer:\tbisectionRatio='" [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ BisectionRatio -> [Char]
forall a. Show a => a -> [Char]
show BisectionRatio
bisectionRatio [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
"' is incompatible with minLength=" [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ MinLength -> [Char]
forall a. Show a => a -> [Char]
show MinLength
minLength [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
"."
| Bool
otherwise = MinLength -> [monoid] -> monoid
forall a. Monoid a => MinLength -> [a] -> a
slave ([monoid] -> MinLength
forall (t :: * -> *) a. Foldable t => t a -> MinLength
length [monoid]
l) [monoid]
l
where
apportion :: Int -> Int
apportion :: MinLength -> MinLength
apportion MinLength
list = (MinLength
list MinLength -> MinLength -> MinLength
forall a. Num a => a -> a -> a
* BisectionRatio -> MinLength
forall a. Ratio a -> a
Data.Ratio.numerator BisectionRatio
bisectionRatio) MinLength -> MinLength -> MinLength
forall a. Integral a => a -> a -> a
`div` BisectionRatio -> MinLength
forall a. Ratio a -> a
Data.Ratio.denominator BisectionRatio
bisectionRatio
slave :: MinLength -> [a] -> a
slave MinLength
len [a]
list
| MinLength
len MinLength -> MinLength -> Bool
forall a. Ord a => a -> a -> Bool
<= MinLength
minLength = [a] -> a
forall a. Monoid a => [a] -> a
Data.Monoid.mconcat [a]
list
| Bool
otherwise = (a -> a -> a) -> (a, a) -> a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> a -> a
forall a. Monoid a => a -> a -> a
Data.Monoid.mappend ((a, a) -> a) -> (([a], [a]) -> (a, a)) -> ([a], [a]) -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Strategy (a, a) -> (a, a) -> (a, a)
forall a. Strategy a -> a -> a
Control.Parallel.Strategies.withStrategy (
Strategy a -> Strategy a -> Strategy (a, a)
forall a b. Strategy a -> Strategy b -> Strategy (a, b)
Control.Parallel.Strategies.parTuple2 Strategy a
forall a. Strategy a
Control.Parallel.Strategies.rseq Strategy a
forall a. Strategy a
Control.Parallel.Strategies.rseq
) ((a, a) -> (a, a))
-> (([a], [a]) -> (a, a)) -> ([a], [a]) -> (a, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (MinLength -> [a] -> a
slave MinLength
cut ([a] -> a) -> ([a] -> a) -> ([a], [a]) -> (a, a)
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** MinLength -> [a] -> a
slave (MinLength
len MinLength -> MinLength -> MinLength
forall a. Num a => a -> a -> a
- MinLength
cut)) (([a], [a]) -> a) -> ([a], [a]) -> a
forall a b. (a -> b) -> a -> b
$ MinLength -> [a] -> ([a], [a])
forall a. MinLength -> [a] -> ([a], [a])
splitAt MinLength
cut [a]
list where
cut :: MinLength
cut = MinLength -> MinLength
apportion MinLength
len
product' :: Num n
=> BisectionRatio
-> MinLength
-> [n]
-> n
product' :: BisectionRatio -> MinLength -> [n] -> n
product' BisectionRatio
bisectionRatio MinLength
minLength = Product n -> n
forall a. Product a -> a
Data.Monoid.getProduct (Product n -> n) -> ([n] -> Product n) -> [n] -> n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. BisectionRatio -> MinLength -> [Product n] -> Product n
forall monoid.
Monoid monoid =>
BisectionRatio -> MinLength -> [monoid] -> monoid
divideAndConquer BisectionRatio
bisectionRatio MinLength
minLength ([Product n] -> Product n)
-> ([n] -> [Product n]) -> [n] -> Product n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (n -> Product n) -> [n] -> [Product n]
forall a b. (a -> b) -> [a] -> [b]
map n -> Product n
forall a. a -> Product a
Data.Monoid.Product
sum' :: Num n
=> BisectionRatio
-> MinLength
-> [n]
-> n
sum' :: BisectionRatio -> MinLength -> [n] -> n
sum' BisectionRatio
bisectionRatio MinLength
minLength = Sum n -> n
forall a. Sum a -> a
Data.Monoid.getSum (Sum n -> n) -> ([n] -> Sum n) -> [n] -> n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. BisectionRatio -> MinLength -> [Sum n] -> Sum n
forall monoid.
Monoid monoid =>
BisectionRatio -> MinLength -> [monoid] -> monoid
divideAndConquer BisectionRatio
bisectionRatio MinLength
minLength ([Sum n] -> Sum n) -> ([n] -> [Sum n]) -> [n] -> Sum n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (n -> Sum n) -> [n] -> [Sum n]
forall a b. (a -> b) -> [a] -> [b]
map n -> Sum n
forall a. a -> Sum a
Data.Monoid.Sum