{-# LANGUAGE CPP #-}
{-
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@]
* Describes a bounded set of, typically integral, quantities.
* Operations have been defined, on the list of /consecutive/ quantities delimited by these endpoints.
* The point is that if the list is composed from /consecutive/ quantities, the intermediate values can be inferred, rather than physically represented.
[@CAVEATS@]
* The API was driven top-down by its caller's requirements, rather than a bottom-up attempt to provide a complete interface.
consequently there may be omissions from the view point of future callers.
* Thought similar to the mathematical concept of an /interval/, the latter technically relates to /real/ numbers; .
* No account has been made for /semi-closed/ or /open/ intervals.
-}
module Factory.Data.Interval(
-- * Types
-- ** Type-synonyms
Interval,
-- * Constants
closedUnitInterval,
-- * Functions
-- divideAndConquer,
elem',
getLength,
normalise,
product',
shift,
splitAt',
toList,
-- ** Accessors
getMinBound,
getMaxBound,
-- ** Constructors
precisely,
-- ** Predicates
isReversed
) where
import Control.Arrow((***), (&&&))
import qualified Data.Monoid
import qualified Data.Ratio
import qualified ToolShed.Pair as Pair
#if MIN_VERSION_parallel(3,0,0)
import qualified Control.Parallel.Strategies
#endif
#if MIN_VERSION_base(4,3,0)
import Data.Tuple(swap)
#else
-- | Swap the components of a pair.
swap :: (a, b) -> (b, a)
swap (a, b) = (b, a)
#endif
-- | Defines a closed (inclusive) interval of consecutive values.
type Interval endPoint = (endPoint, endPoint)
-- | Accessor.
{-# INLINE getMinBound #-}
getMinBound :: Interval endPoint -> endPoint
getMinBound = fst
-- | Accessor.
{-# INLINE getMaxBound #-}
getMaxBound :: Interval endPoint -> endPoint
getMaxBound = snd
-- | Construct the interval from a single value.
precisely :: endPoint -> Interval endPoint
precisely = id &&& id
-- | Construct the /closed unit-interval/; .
closedUnitInterval :: Num n => Interval n
closedUnitInterval = (0, 1)
-- | Shift of both /end-points/ of the /interval/ by the specified amount.
shift :: Num endPoint
=> endPoint -- ^ The magnitude of the require shift.
-> Interval endPoint -- ^ The interval to be shifted.
-> Interval endPoint
shift i = Pair.mirror (+ i)
-- | 'True' if the specified value is within the inclusive bounds of the /interval/.
elem' :: Ord endPoint => endPoint -> Interval endPoint -> Bool
elem' x = Pair.both . ((<= x) *** (x <=))
-- | 'True' if 'getMinBound' exceeds 'getMaxBound' extent.
isReversed :: Ord endPoint => Interval endPoint -> Bool
isReversed = uncurry (>)
-- | Swap the /end-points/ where they were originally reversed, but otherwise do nothing.
normalise :: Ord endPoint => Interval endPoint -> Interval endPoint
normalise b
| isReversed b = swap b
| otherwise = b
-- | Bisect the /interval/ at the specified /end-point/; which should be between the two existing /end-points/.
splitAt' :: (Num endPoint, Ord endPoint) => endPoint -> Interval endPoint -> (Interval endPoint, Interval endPoint)
splitAt' i interval@(l, r)
| any ($ i) [(< l), (>= r)] = error $ "Factory.Data.Interval.splitAt':\tunsuitable index=" ++ show i ++ " for interval=" ++ show interval ++ "."
| otherwise = ((l, i), (i + 1, r))
-- | The length of 'toList'.
{-# INLINE getLength #-}
getLength :: (Num endPoint, Ord endPoint) => Interval endPoint -> endPoint
getLength (l, r) = r + 1 - l
-- | Converts 'Interval' to a list by enumerating the values.
{-# INLINE toList #-}
toList :: Enum endPoint => Interval endPoint -> [endPoint]
toList = uncurry enumFromTo
{- |
* Reduces 'Interval' to a single integral value encapsulated in a 'Data.Monoid.Monoid',
using a /divide-and-conquer/ strategy,
bisecting the /interval/ and recursively evaluating each part; .
* By choosing a 'ratio' 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 length,
after which the 'Interval' are expanded into the corresponding list, and the /monoid/'s binary operator is directly /folded/ over it.
* One can view this as a ,
in which 'Interval' 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 :: (Integral i, Data.Monoid.Monoid monoid)
=> (i -> monoid) -- ^ The monoid's constructor.
-> Data.Ratio.Ratio i -- ^ The ratio of the original span, at which to bisect the 'Interval'.
-> i -- ^ For efficiency, the /interval/ will not be bisected, when it's length has been reduced to this value.
-> Interval i
-> monoid -- ^ The resulting scalar.
divideAndConquer monoidConstructor ratio minLength
| any ($ ratio) [
(< 0),
(>= 1)
] = error $ "Factory.Data.Interval.divideAndConquer:\tunsuitable ratio='" ++ show ratio ++ "'."
| minLength < 1 = error $ "Factory.Data.Interval.divideAndConquer:\tunsuitable minLength=" ++ show minLength ++ "."
| otherwise = slave
where
slave interval@(l, r)
| getLength interval <= minLength = Data.Monoid.mconcat . map monoidConstructor $ toList interval --Fold the monoid's binary operator over the delimited list.
| otherwise = uncurry Data.Monoid.mappend .
#if MIN_VERSION_parallel(3,0,0)
Control.Parallel.Strategies.withStrategy (
Control.Parallel.Strategies.parTuple2 Control.Parallel.Strategies.rseq Control.Parallel.Strategies.rseq
) .
#endif
Pair.mirror slave $ splitAt' (
l + (r - l) * Data.Ratio.numerator ratio `div` Data.Ratio.denominator ratio --Use the ratio to generate the split-index.
) interval --Apply the monoid's binary operator to the two operands resulting from bisection.
{- |
* Multiplies the consecutive sequence of integers within 'Interval'.
* Since the result can be large, 'divideAndConquer' is used to form operands of a similar order of magnitude,
thus improving the efficiency of the big-number multiplication.
-}
product' :: Integral i
=> Data.Ratio.Ratio i -- ^ The ratio at which to bisect the 'Interval'.
-> i -- ^ For efficiency, the /interval/ will not be bisected, when it's length has been reduced to this value.
-> Interval i
-> i -- ^ The resulting product.
product' ratio minLength interval
| elem' 0 interval = 0
| otherwise = Data.Monoid.getProduct $ divideAndConquer Data.Monoid.Product ratio minLength interval