data-interval 0.3.0 → 0.4.0

raw patch · 3 files changed

+80/−4 lines, 3 files

Files

data-interval.cabal +10/−2
src/Data/Interval.hs +34/−1
test/TestInterval.hs +36/−1

data-interval.cabal view

@@ -1,5 +1,5 @@ Name:		data-interval-Version:	0.3.0+Version:	0.4.0 License:	BSD3 License-File:	COPYING Author:		Masahiro Sakai (masahiro.sakai@gmail.com)@@ -11,6 +11,11 @@    Unlike the intervals package (<http://hackage.haskell.org/package/intervals>),    this package provides both open and closed intervals and is intended to be used    with Rational.+   .+   Changes in 0.4.0+   .+   * add simplestRationalWithin :: RealFrac r => Interval r -> Maybe Rational+ Bug-Reports:	https://github.com/msakai/data-interval/issues Extra-Source-Files:    README.md@@ -39,5 +44,8 @@   Main-is:           TestInterval.hs   Build-depends:     base >=4 && <5, containers, data-interval, test-framework, test-framework-th, test-framework-hunit, test-framework-quickcheck2, HUnit, QuickCheck >=2 && <3   Default-Language: Haskell2010-  Other-Extensions: TemplateHaskell+  Other-Extensions:+     TemplateHaskell+     ScopedTypeVariables+

src/Data/Interval.hs view

@@ -1,4 +1,4 @@-{-# LANGUAGE ScopedTypeVariables, DeriveDataTypeable #-}+{-# LANGUAGE ScopedTypeVariables, DeriveDataTypeable, DoAndIfThenElse #-} ----------------------------------------------------------------------------- -- | -- Module      :  Data.Interval@@ -58,6 +58,7 @@    -- * Operations   , pickup+  , simplestRationalWithin   ) where  import Algebra.Lattice@@ -69,6 +70,7 @@ import Data.List hiding (null) import Data.Maybe import Data.Monoid+import Data.Ratio import Data.Typeable import Prelude hiding (null) @@ -305,6 +307,37 @@     LT -> Just $ (x1+x2) / 2     EQ -> if in1 && in2 then Just x1 else Nothing pickup x = Nothing++-- | 'simplestRationalWithin' returns the simplest rational number within the interval.+-- A rational number @y@ is said to be /simpler/ than another @y'@ if+--+-- * @'abs' ('numerator' y) <= 'abs' ('numerator' y')@, and+--+-- * @'denominator' y <= 'denominator' y'@.+-- +-- (see also 'approxRational')+--+simplestRationalWithin :: RealFrac r => Interval r -> Maybe Rational+simplestRationalWithin i | null i = Nothing+simplestRationalWithin i +  | 0 <! i    = Just $ go i +  | i <! 0    = Just $ - go (- i)+  | otherwise = assert (0 `member` i) $ Just $ 0+  where+    go i+      | fromInteger lb_floor       `member'` i = fromInteger lb_floor+      | fromInteger (lb_floor + 1) `member'` i = fromInteger (lb_floor + 1)+      | otherwise = fromInteger lb_floor + recip (go (recip (i - singleton (fromInteger lb_floor))))+      where+        Finite lb = lowerBound i+        lb_floor  = floor lb++    member' :: (Real r, Fractional r) => Rational -> Interval r -> Bool+    member' x (Interval (x1,in1) (x2,in2)) = condLB && condUB+      where+        x' = fromRational x+        condLB = if in1 then x1 <= Finite x' else x1 < Finite x'+        condUB = if in2 then Finite x' <= x2 else Finite x' < x2  -- | For all @x@ in @X@, @y@ in @Y@. @x '<' y@ (<!) :: Real r => Interval r -> Interval r -> Bool

test/TestInterval.hs view

@@ -1,4 +1,4 @@-{-# LANGUAGE TemplateHaskell #-}+{-# LANGUAGE TemplateHaskell, ScopedTypeVariables #-}  import Control.Monad import Data.Maybe@@ -172,6 +172,41 @@ --   forAll intervals $ \b -> --     Interval.isSubsetOf a b && Interval.isSubsetOf b a --     ==> a == b++{--------------------------------------------------------------------+  simplestRationalWithin+--------------------------------------------------------------------}++prop_simplestRationalWithin_and_approxRational =+  forAll arbitrary $ \(r::Rational) ->+    forAll arbitrary $ \(eps::Rational) ->+      eps > 0 ==> Interval.simplestRationalWithin (Finite (r-eps) <=..<= Finite (r+eps)) == Just (approxRational r eps)++prop_simplestRationalWithin_singleton =+  forAll arbitrary $ \(r::Rational) ->+      Interval.simplestRationalWithin (Interval.singleton r) == Just r++case_simplestRationalWithin_empty =+  Interval.simplestRationalWithin Interval.empty @?= Nothing++case_simplestRationalWithin_test1 =+  Interval.simplestRationalWithin (Finite (-0.5 :: Rational) <=..<= Finite 0.5) @?= Just 0++case_simplestRationalWithin_test2 =+  Interval.simplestRationalWithin (Finite (2 :: Rational) <..< Finite 3) @?= Just 2.5++case_simplestRationalWithin_test2' =+  Interval.simplestRationalWithin (Finite (-3 :: Rational) <..< Finite (-2)) @?= Just (-2.5)++case_simplestRationalWithin_test3 =+  Interval.simplestRationalWithin (Finite (1.4142135623730951 :: Rational) <..< Finite 1.7320508075688772) @?= Just 1.5++-- http://en.wikipedia.org/wiki/Best_rational_approximation#Best_rational_approximations+case_simplestRationalWithin_test4 =+  Interval.simplestRationalWithin (Finite (3.14155 :: Rational) <..< Finite 3.14165) @?= Just (355/113) ++case_simplestRationalWithin_test5 =+  Interval.simplestRationalWithin (Finite (1.1e-20 :: Rational) <..< Finite (1.2e-20)) @?= Just (1/83333333333333333334)  {--------------------------------------------------------------------   pickup