{-# LANGUAGE EmptyDataDecls #-}
{-|
The purpose of this module is to provide newtype wrapper that allows one to effectively override the equality operator of a value so that it is /approximate/ rather than /exact/. For example, the type
> type ApproximateDouble = AbsolutelyApproximateValue (Digits Five) Double
defines an alias for a wrapper containing 'Double's such that two doubles are equal if they are equal to within five decimals of accuracy; for example, we have that
> 1 == (1+10^^(-6) :: ApproximateDouble)
evaluates to 'True'. Note that we did not need to wrap the value @1+10^^(-6)@ since 'AbsolutelyApproximateValue' is an instance of 'Num'. For convenience, 'Num' as well as many other of the numerical classes such as 'Real' and 'Floating' have all been derived for the wrappers defined in this package so that one can conveniently use the wrapped values in the same way as one would use the values themselves.
Two kinds of wrappers are provided by this package.
* 'AbsolutelyApproximateValue' wraps values that are considered to be equal if their absolute difference falls within the specified tolerance.
* 'RelativelyApproximateValue' wraps values that are considered to be equal if the absolute difference between the values divided by the average of the absolute values is within the given relative tolerance, /or/ if the absolute value of both values falls within the zero tolerance; the latter case is checked because otherwise no value, no matter how small, would be approximately equal to zero.
The tolerance is specified through a type annotation. One can use any annotation that one wishes as long as the type is an instance of 'AbsoluteTolerance' (for absolute tolerances) and/or 'RelativeTolerance' and 'ZeroTolerance' (for relative tolerances). For convenience, this package provides the type 'Digits' that allows one to specify the tolerance in terms of the number of digits, making use of type-level natural numbers. The annotation @Digits n@ sets the tolerance to @10^-n@, so that in the case of the absolute tolerance and the zero tolerance @n@ is the number of decimal places that numbers have to match to be equal to respectively either each other or to zero, and in the case of relative tolerance @n@ is (roughly) the number of leading digits that two numbers have to match in order to be equal to each other.
-}
module Data.Eq.Approximate
(-- * Type wrappers
AbsolutelyApproximateValue(..)
,RelativelyApproximateValue(..)
-- * Classes for tolerance type annotations
-- $classes
-- ** Absolute tolerance
,AbsoluteTolerance(..)
,getAbsoluteTolerance
-- ** Relative tolerance
,RelativeTolerance(..)
,getRelativeTolerance
-- ** Zero tolerance
,ZeroTolerance(..)
,getZeroTolerance
-- * Tolerance annotations using Digits
,Digits(..)
,unwrapDigits
,toleranceFromDigits
) where
import Control.Arrow
import Data.Function
import Text.Printf
import TypeLevel.NaturalNumber
{-|
The newtype 'AbsolutelyApproximateValue' is a wrapper that can contain an arbitrary value tagged with a tolerance; two values are equal to each other if the absolute difference is less than or equal to this tolerance. The type annotation @absolute_tolerance@, which must be an instance of 'AbsoluteTolerance', specifies the tolerance. For convenience, one may specify the tolerance using the type @Digits n@ where @n@ is a type-level natural specifying the number of decimals in the tolerance (i.e., @Digits Four@ specifies a tolerance of 0.0001).
It is recommended that one use this wrapper by creating aliases, such as
> type ApproximateDouble = AbsolutelyApproximateValue (Digits Five)
> wrapAD :: Double -> ApproximateDouble
> wrapAD = AbsolutelyApproximateValue
> unwrapAD :: ApproximateDouble -> Double
> unwrapAD = unwrapAbsolutelyApproximateValue
You can then replace the type 'Double' in your code with the type alias @ApproximateDouble@ to get the feature of approximate equality. Most of the time you will find that you do not need to use wrapping functions to construct wrapped values since 'AbsolutelyApproximateValue' is an instance of whatever numerical types the wrapped value is, so that for example @1 + sqrt 2/3@ is already a value of type @ApproximateDouble@ without needing to be wrapped first.
-}
newtype AbsolutelyApproximateValue absolute_tolerance value =
AbsolutelyApproximateValue { unwrapAbsolutelyApproximateValue :: value }
{-|
The newtype 'RelativelyApproximateValue' is a wrapper that can contain an arbitrary value tagged with a zero tolerance and a relative tolerance; two values are equal to each other if their absolute values are both less than or equal to the zero tolerance, or if the absolute difference between them divided by the average of the absolute values is less than or equal to the relative tolerance.
The type annotation @zero_tolerance@, which must be an instance of 'ZeroTolerance', specifies the tolerance within which a value is considered to be equal to zero. For convenience, one may specify the tolerance using the type @Digits n@ where @n@ is a type-level natural specifying the number of decimals in the tolerance (i.e., @Digits Four@ specifies a tolerance of 0.0001).
The type annotation @relative_tolerance@, which must be an instance of 'RelativeTolerance', specifies the relative tolerance within which two values that are not approximately equal to zero are considered to be equal to each other. For convenience, as with the zero tolerance, one may specify the relative tolerance using the type @Digits n@ where @n@ is a type-level natural specifying the number of decimals in the tolerance (i.e., @Digits Four@ specifies a relative tolerance of 0.0001, so that two values are equal if they agree to the first four leading digits).
It is recommended that one use this wrapper by creating aliases, such as
> type ApproximateDouble = RelativelyApproximateValue (Digits Five) (Digits Five)
> wrapAD :: Double -> ApproximateDouble
> wrapAD = RelativelyApproximateValue
> unwrapAD :: ApproximateDouble -> Double
> unwrapAD = unwrapRelativelyApproximateValue
You can then replace the type 'Double' in your code with the type alias @ApproximateDouble@ to get the feature of approximate equality. Most of the time you will find that you do not need to use wrapping functions to construct wrapped values since 'RelativelyApproximateValue' is an instance of whatever numerical types the wrapped value is, so that for example @1 + sqrt 2/3@ is already a value of type @ApproximateDouble@ without needing to be wrapped first.
-}
newtype RelativelyApproximateValue zero_tolerance relative_tolerance value =
RelativelyApproximateValue { unwrapRelativelyApproximateValue :: value }
{-|
Digits is a type constructor that can be used to specify tolerances using type-level natural numbers. Annotating a wrapper with the type @Digits n@ specifies that the corresponding tolerance has a numerical value of @10^(-n)@.
-}
data Digits n
-- $classes
-- The classes in this section are used to associate numerical tolerance information with the types that are used to annotate the type wrappers 'AbsolutelyApproximateValue' and 'RelativelyApproximateValue'. One typically should not need to use them since the annotation @Digits n@ should cover most common cases.
--
-- One might consider hand-rolling instances in order to obtain faster code (since this will bypass the type-level natural numbers), however I have found in my own experience that using hand-rolled instances rather than @Digits Five@ in my own program resulted in code that was one or two orders of magnitude /slower/ than simply using 'Digits'. This is not to claim that hand-rolled instances can /never/ be faster than using 'Digits', but one should be careful about trying this without checking whether there really is an improvement. In general, 'Digits' seems to be fast enough in the common case that hand-rolling instances for speed is unlikely to be worth the trouble.
{-|
The class 'AbsoluteTolerance' is used to define the absolute tolerances associated with types that will be used as absolute tolerance type annotations in 'AbsolutelyApproximateValue'.
-}
class AbsoluteTolerance absolute_tolerance where
{-|
This method retrieves the numerical absolute tolerance associated with the type; it should be a constant function.
-}
absoluteToleranceOf ::
Fractional value =>
AbsolutelyApproximateValue absolute_tolerance value ->
value
{-|
The class 'RelativeTolerance' is used to define the relative tolerances associated with types that will be used as relative tolerance type annotations in 'RelativelyApproximateValue'.
-}
class RelativeTolerance relative_tolerance where
{-|
This method retrieves the numerical relative tolerance associated with the type; it should be a constant function.
-}
relativeToleranceOf ::
Fractional value =>
RelativelyApproximateValue zero_tolerance relative_tolerance value ->
value
{-|
The class 'ZeroTolerance' is used to define the numerical zero tolerances associated with types that will be used as zero tolerance type annotations in 'RelativelyApproximateValue'.
-}
class ZeroTolerance zero_tolerance where
{-|
This method retrieves the numerical zero tolerance associated with the type; it should be a constant function.
-}
zeroToleranceOf ::
Fractional value =>
RelativelyApproximateValue zero_tolerance relative_tolerance value ->
value
instance (AbsoluteTolerance tolerance
,Ord value
,Fractional value
) =>
Show (AbsolutelyApproximateValue tolerance value)
where
show x =
show (unwrapAAV x)
++ " +/- " ++
show (absoluteToleranceOf x)
instance (AbsoluteTolerance tolerance
,Ord value
,Fractional value
) =>
Eq (AbsolutelyApproximateValue tolerance value)
where
a == b = abs (unwrapAAV a - unwrapAAV b) <= absoluteToleranceOf a
instance (AbsoluteTolerance tolerance
,Ord value
,Fractional value
) =>
Ord (AbsolutelyApproximateValue tolerance value)
where
compare a b
| a == b = EQ
| otherwise = (compare `on` unwrapAAV) a b
instance Enum value => Enum (AbsolutelyApproximateValue tolerance value) where
succ = liftAAV1 succ
pred = liftAAV1 pred
toEnum = wrapAAV . toEnum
fromEnum = unwrapAAVAndApply fromEnum
enumFrom = map wrapAAV . enumFrom . unwrapAAV
enumFromThen a b = map wrapAAV (enumFromThen (unwrapAAV a) (unwrapAAV b))
enumFromTo a b = map wrapAAV (enumFromTo (unwrapAAV a) (unwrapAAV b))
enumFromThenTo a b c = map wrapAAV (enumFromThenTo (unwrapAAV a) (unwrapAAV b) (unwrapAAV c))
instance
(AbsoluteTolerance tolerance
,Ord value
,Fractional value
) => Num (AbsolutelyApproximateValue tolerance value)
where
(+) = liftAAV2 (+)
(*) = liftAAV2 (*)
(-) = liftAAV2 (-)
negate = liftAAV1 negate
abs = liftAAV1 abs
signum = liftAAV1 signum
fromInteger = wrapAAV . fromInteger
instance
(AbsoluteTolerance tolerance
,Ord value
,Fractional value
,Real value
) => Real (AbsolutelyApproximateValue tolerance value)
where
toRational = unwrapAAVAndApply toRational
instance
(AbsoluteTolerance tolerance
,Ord value
,Fractional value
,Integral value
) => Integral (AbsolutelyApproximateValue tolerance value)
where
quot = liftAAV2 quot
rem = liftAAV2 rem
div = liftAAV2 div
mod = liftAAV2 mod
quotRem a b = (wrapAAV *** wrapAAV) $ (quotRem `on` unwrapAAV) a b
divMod a b = (wrapAAV *** wrapAAV) $ (divMod `on` unwrapAAV) a b
toInteger = toInteger . unwrapAAV
instance
(AbsoluteTolerance tolerance
,Ord value
,Fractional value
) => Fractional (AbsolutelyApproximateValue tolerance value)
where
(/) = liftAAV2 (/)
recip = liftAAV1 recip
fromRational = wrapAAV . fromRational
instance
(AbsoluteTolerance tolerance
,Ord value
,Floating value
) => Floating (AbsolutelyApproximateValue tolerance value)
where
pi = wrapAAV pi
exp = liftAAV1 exp
sqrt = liftAAV1 sqrt
log = liftAAV1 log
(**) = liftAAV2 (**)
logBase = liftAAV2 logBase
sin = liftAAV1 sin
tan = liftAAV1 tan
cos = liftAAV1 cos
asin = liftAAV1 asin
atan = liftAAV1 atan
acos = liftAAV1 acos
sinh = liftAAV1 sinh
tanh = liftAAV1 tanh
cosh = liftAAV1 cosh
asinh = liftAAV1 asinh
atanh = liftAAV1 atanh
acosh = liftAAV1 acosh
instance
(AbsoluteTolerance tolerance
,Ord value
,RealFrac value
) => RealFrac (AbsolutelyApproximateValue tolerance value)
where
properFraction = second wrapAAV . unwrapAAVAndApply properFraction
truncate = unwrapAAVAndApply truncate
round = unwrapAAVAndApply round
ceiling = unwrapAAVAndApply ceiling
floor = unwrapAAVAndApply floor
instance
(AbsoluteTolerance tolerance
,Ord value
,RealFloat value
) => RealFloat (AbsolutelyApproximateValue tolerance value)
where
floatRadix = unwrapAAVAndApply floatRadix
floatDigits = unwrapAAVAndApply floatDigits
floatRange = unwrapAAVAndApply floatRange
decodeFloat = unwrapAAVAndApply decodeFloat
encodeFloat x y = wrapAAV (encodeFloat x y)
exponent = unwrapAAVAndApply exponent
significand = liftAAV1 significand
scaleFloat i = liftAAV1 (scaleFloat i)
isNaN = unwrapAAVAndApply isNaN
isInfinite = unwrapAAVAndApply isInfinite
isDenormalized = unwrapAAVAndApply isDenormalized
isNegativeZero = unwrapAAVAndApply isNegativeZero
isIEEE = unwrapAAVAndApply isIEEE
atan2 = liftAAV2 atan2
instance (ZeroTolerance zerotol
,RelativeTolerance reltol
,Ord value
,Fractional value
) =>
Show (RelativelyApproximateValue zerotol reltol value)
where
show a@(RelativelyApproximateValue x) =
if a == 0
then "0 +/- " ++ show (zeroToleranceOf a)
else show x ++ " +/- " ++ show (x * relativeToleranceOf a * 100)
instance (ZeroTolerance zerotol
,RelativeTolerance reltol
,Ord value
,Fractional value
) =>
Eq (RelativelyApproximateValue zerotol reltol value)
where
a == b =
case (unwrapRAV a,unwrapRAV b) of
(0,0) -> True
(0,y) -> abs y <= zerotol
(x,0) -> abs x <= zerotol
(x,y)
| abs x <= zerotol && abs y <= zerotol -> True
| otherwise -> abs (x - y) / (abs x + abs y) * 2 <= reltol
where
zerotol = zeroToleranceOf a
reltol = relativeToleranceOf a
instance (ZeroTolerance zerotol
,RelativeTolerance reltol
,Ord value
,Fractional value
) =>
Ord (RelativelyApproximateValue zerotol reltol value)
where
compare a b
| a == b = EQ
| otherwise = (compare `on` unwrapRAV) a b
instance Enum value => Enum (RelativelyApproximateValue zerotol reltol value) where
succ = liftRAV1 succ
pred = liftRAV1 pred
toEnum = wrapRAV . toEnum
fromEnum = unwrapRAVAndApply fromEnum
enumFrom = map wrapRAV . enumFrom . unwrapRAV
enumFromThen a b = map wrapRAV (enumFromThen (unwrapRAV a) (unwrapRAV b))
enumFromTo a b = map wrapRAV (enumFromTo (unwrapRAV a) (unwrapRAV b))
enumFromThenTo a b c = map wrapRAV (enumFromThenTo (unwrapRAV a) (unwrapRAV b) (unwrapRAV c))
instance
(ZeroTolerance zerotol
,RelativeTolerance reltol
,Ord value
,Fractional value
) => Num (RelativelyApproximateValue zerotol reltol value)
where
(+) = liftRAV2 (+)
(*) = liftRAV2 (*)
(-) = liftRAV2 (-)
negate = liftRAV1 negate
abs = liftRAV1 abs
signum = liftRAV1 signum
fromInteger = wrapRAV . fromInteger
instance
(ZeroTolerance zerotol
,RelativeTolerance reltol
,Ord value
,Fractional value
,Real value
) => Real (RelativelyApproximateValue zerotol reltol value)
where
toRational = unwrapRAVAndApply toRational
instance
(ZeroTolerance zerotol
,RelativeTolerance reltol
,Ord value
,Fractional value
,Integral value
) => Integral (RelativelyApproximateValue zerotol reltol value)
where
quot = liftRAV2 quot
rem = liftRAV2 rem
div = liftRAV2 div
mod = liftRAV2 mod
quotRem a b = (wrapRAV *** wrapRAV) $ (quotRem `on` unwrapRAV) a b
divMod a b = (wrapRAV *** wrapRAV) $ (divMod `on` unwrapRAV) a b
toInteger = toInteger . unwrapRAV
instance
(ZeroTolerance zerotol
,RelativeTolerance reltol
,Ord value
,Fractional value
) => Fractional (RelativelyApproximateValue zerotol reltol value)
where
(/) = liftRAV2 (/)
recip = liftRAV1 recip
fromRational = wrapRAV . fromRational
instance
(ZeroTolerance zerotol
,RelativeTolerance reltol
,Ord value
,Floating value
) => Floating (RelativelyApproximateValue zerotol reltol value)
where
pi = wrapRAV pi
exp = liftRAV1 exp
sqrt = liftRAV1 sqrt
log = liftRAV1 log
(**) = liftRAV2 (**)
logBase = liftRAV2 logBase
sin = liftRAV1 sin
tan = liftRAV1 tan
cos = liftRAV1 cos
asin = liftRAV1 asin
atan = liftRAV1 atan
acos = liftRAV1 acos
sinh = liftRAV1 sinh
tanh = liftRAV1 tanh
cosh = liftRAV1 cosh
asinh = liftRAV1 asinh
atanh = liftRAV1 atanh
acosh = liftRAV1 acosh
instance
(ZeroTolerance zerotol
,RelativeTolerance reltol
,Ord value
,RealFrac value
) => RealFrac (RelativelyApproximateValue zerotol reltol value)
where
properFraction = second wrapRAV . unwrapRAVAndApply properFraction
truncate = unwrapRAVAndApply truncate
round = unwrapRAVAndApply round
ceiling = unwrapRAVAndApply ceiling
floor = unwrapRAVAndApply floor
instance
(ZeroTolerance zerotol
,RelativeTolerance reltol
,Ord value
,RealFloat value
) => RealFloat (RelativelyApproximateValue zerotol reltol value)
where
floatRadix = unwrapRAVAndApply floatRadix
floatDigits = unwrapRAVAndApply floatDigits
floatRange = unwrapRAVAndApply floatRange
decodeFloat = unwrapRAVAndApply decodeFloat
encodeFloat x y = wrapRAV (encodeFloat x y)
exponent = unwrapRAVAndApply exponent
significand = liftRAV1 significand
scaleFloat i = liftRAV1 (scaleFloat i)
isNaN = unwrapRAVAndApply isNaN
isInfinite = unwrapRAVAndApply isInfinite
isDenormalized = unwrapRAVAndApply isDenormalized
isNegativeZero = unwrapRAVAndApply isNegativeZero
isIEEE = unwrapRAVAndApply isIEEE
atan2 = liftRAV2 atan2
instance NaturalNumber n => AbsoluteTolerance (Digits n) where
absoluteToleranceOf =
toleranceFromDigits
.
getAbsoluteTolerance
instance NaturalNumber n => RelativeTolerance (Digits n) where
relativeToleranceOf =
toleranceFromDigits
.
getRelativeTolerance
instance NaturalNumber n => ZeroTolerance (Digits n) where
zeroToleranceOf =
toleranceFromDigits
.
getZeroTolerance
{-|
This is a convenience (constant) function for extracting the type-level natural number contained within the 'Digits' type constructor; it returns the value 'undefined', so don't try to evaluate the result.
-}
unwrapDigits :: Digits n -> n
unwrapDigits _ = undefined
{-|
This is a convenience (constant) function that computes the numerical tolerance specified by @Digits n@, which is @10^(-n)@.
-}
toleranceFromDigits :: NaturalNumber n => Fractional value => Digits n -> value
toleranceFromDigits =
recip
.
fromInteger
.
((10::Integer) ^)
.
naturalNumberAsInt
.
unwrapDigits
{-|
This is a convenience (constant) function for extracting the relative tolerance type annotation from 'AbsolutelyApproximateValue'; it returns the value 'undefined', so don't try to evaluate the result.
-}
getAbsoluteTolerance ::
AbsolutelyApproximateValue absolute_tolerance value ->
absolute_tolerance
getAbsoluteTolerance = undefined
{-|
This is a convenience (constant) function for extracting the relative tolerance type annotation from 'RelativelyApproximateValue'; it returns the value 'undefined', so don't try to evaluate the result.
-}
getRelativeTolerance ::
RelativelyApproximateValue zero_tolerance relative_tolerance value ->
relative_tolerance
getRelativeTolerance = undefined
{-|
This is a convenience (constant) function for extracting the zero tolerance type annotation from 'RelativelyApproximateValue'; it returns the value 'undefined', so don't try to evaluate the result.
-}
getZeroTolerance ::
RelativelyApproximateValue zero_tolerance relative_tolerance value ->
zero_tolerance
getZeroTolerance = undefined
{-# INLINE wrapAAV #-}
{-# INLINE unwrapAAV #-}
{-# INLINE liftAAV1 #-}
{-# INLINE liftAAV2 #-}
{-# INLINE unwrapAAVAndApply #-}
wrapAAV = AbsolutelyApproximateValue
unwrapAAV = unwrapAbsolutelyApproximateValue
liftAAV1 f = wrapAAV . f . unwrapAAV
liftAAV2 f a b = wrapAAV (f (unwrapAAV a) (unwrapAAV b))
unwrapAAVAndApply f = f . unwrapAAV
{-# INLINE wrapRAV #-}
{-# INLINE unwrapRAV #-}
{-# INLINE liftRAV1 #-}
{-# INLINE liftRAV2 #-}
{-# INLINE unwrapRAVAndApply #-}
wrapRAV = RelativelyApproximateValue
unwrapRAV = unwrapRelativelyApproximateValue
liftRAV1 f = wrapRAV . f . unwrapRAV
liftRAV2 f a b = wrapRAV (f (unwrapRAV a) (unwrapRAV b))
unwrapRAVAndApply f = f . unwrapRAV