peano-inf 0.1 → 0.2

raw patch · 2 files changed

+146/−32 lines, 2 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Number/Peano/Inf.hs +144/−30
• peano-inf.cabal +2/−2

@@ -10,6 +10,9 @@     ( Nat (Zero, Succ)     , infinity     , isInfinity+    , diff+    , zeroDiff+    , infDiff     , (-|)     ) where @@ -26,7 +29,7 @@ infinity :: Nat infinity = Inf --- | True for @(infinity)@, @(5 + 4 * infinity)@ etc. Evaluates to bottom for @(genericLength [1..])@.+-- | True on @(infinity)@, @(5 + 4 * infinity)@ etc. Evaluates to bottom on @(genericLength [1..])@.  isInfinity :: Nat -> Bool isInfinity Zero = False@@ -37,7 +40,7 @@      Zero   == Zero   = True     Succ n == Succ m = n == m-    Inf    == Inf    = error "Nat: infinity == infinity"+    Inf    == Inf    = error "Number.Peano.Inf: infinity == infinity."     Succ n == Inf    = n == Inf      Inf    == Succ m = Inf == m      _      == _      = False@@ -48,25 +51,25 @@     Zero   `compare` _      = LT     _      `compare` Zero   = GT     Succ n `compare` Succ m = n `compare` m-    Inf    `compare` Inf    = error "Nat: infinity `compare` infinity"+    Inf    `compare` Inf    = error "Number.Peano.Inf: infinity `compare` infinity."     Inf    `compare` Succ m = Inf `compare` m     Succ n `compare` Inf    = n `compare` Inf      _      < Zero   = False     Zero   < _      = True     Succ n < Succ m = n < m-    Inf    < Inf    = error "Nat: infinity < infinity"+    Inf    < Inf    = error "Number.Peano.Inf: infinity < infinity."     Inf    < Succ m = Inf < m     Succ n < Inf    = n < Inf -    x > y = y < x+    n > m = m < n -    x <= y = not (y < x)+    n <= m = not (m < n) -    x >= y = not (x < y)+    n >= m = not (n < m) -    Zero   `max` x      = x-    x      `max` Zero   = x+    Zero   `max` m      = m+    n      `max` Zero   = n     Succ n `max` Succ m = Succ (n `max` m)     _      `max` _      = Inf @@ -76,30 +79,77 @@     Inf    `min` m      = m     n      `min` Inf    = n ++toInteger' :: Nat -> Maybe Integer+toInteger' n = f 0 n where++    f i Zero = Just i+    f i (Succ m) = i' `seq` f i' m  where i' = i+1+    f _ Inf = Nothing++ instance Show Nat where -    show Inf = "infinity"-    show x   = show $ toInteger x+    show n = case toInteger' n of+        Just i  -> show i+        Nothing -> "infinity" --- | Subtraction maximized to 0. For example, @(5 -| 8  ==  0)@.+-- | Difference of two natural numbers: the result is either positive or negative.+diff +    :: Nat             -- ^ n+    -> Nat             -- ^ m+    -> Either Nat Nat  -- ^ n >= m: Left (n-m),  n < m: Right (m-n) +n      `diff` Zero   = Left  n +Zero   `diff` m      = Right m+Succ n `diff` Succ m = n `diff` m+Inf    `diff` Inf    = error "Number.Peano.Inf: infinity - infinity."+Inf    `diff` Succ m = Inf `diff` m+Succ n `diff` Inf    = n `diff` Inf+++-- | Variant of @diff@: @infinity `infDiff` infinity  ==  Left infinity@.+infDiff+    :: Nat             -- ^ n+    -> Nat             -- ^ m+    -> Either Nat Nat  -- ^ n >= m: Left (n-m),  n < m: Right (m-n)++Inf    `infDiff` _      = Left Inf+Succ n `infDiff` Succ m = n `infDiff` m+Succ n `infDiff` Inf    = n `infDiff` Inf+n      `infDiff` Zero   = Left  n +Zero   `infDiff` m      = Right m+++-- | Variant of @diff@: @infinity `zeroDiff` infinity  ==  Left Zero@.+zeroDiff+    :: Nat             -- ^ n+    -> Nat             -- ^ m+    -> Either Nat Nat  -- ^ n >= m: Left (n-m),  n < m: Right (m-n)++n      `zeroDiff` Zero   = Left  n +Zero   `zeroDiff` m      = Right m+Succ n `zeroDiff` Succ m = n `zeroDiff` m+Inf    `zeroDiff` Inf    = Left Zero+Inf    `zeroDiff` Succ m = Inf `zeroDiff` m+Succ n `zeroDiff` Inf    = n `zeroDiff` Inf++++-- | Non-negative subtraction. For example, @(5 -| 8  ==  0)@.+ infixl 6 -| (-|) :: Nat -> Nat -> Nat-Inf    -| Inf    = error "Nat: infinity -| infinity"-Inf    -| _      = Inf-Succ n -| Succ m = n -| m-n      -| Zero   = n-_      -| _      = Zero+n -| m = case n `diff` m of+    Left k  -> k+    Right _ -> Zero   instance Num Nat where -    Inf    - Inf    = error "Nat: infinity - infinity"-    Inf    - _      = Inf-    Succ n - Succ m = n - m-    n      - Zero   = n-    _      - Inf    = error "Nat: n - inifinty"-    Zero   - Succ _ = error "Nat: 0 - succ n"+    n - m = case n `diff` m of+        Left k  -> k+        Right _ -> error "Number.Peano.Inf: 0 - succ n."      Zero   + m      = m     Succ n + m      = Succ (n + m)@@ -109,34 +159,98 @@     Zero   * _ = Zero     Inf    * _ = Inf -    fromInteger i | i < 0 = error "Nat: fromInteger on negative value."+    fromInteger i | i < 0 = error "Number.Peano.Inf: fromInteger on negative value."     fromInteger i = iterate Succ Zero !! fromInteger i -    abs x = x+    abs n = n      signum Zero = Zero     signum _    = Succ Zero  instance Enum Nat where -    toEnum i | i < 0 = error "Nat: toEnum on negative value."+    succ = Succ++    pred Inf = Inf+    pred (Succ n) = n+    pred Zero = error "Number.Peano.Inf: pred 0."++    toEnum i | i < 0 = error "Number.Peano.Inf: toEnum on negative value."     toEnum i = iterate Succ Zero !! i +    enumFrom n = enumFromTo n Inf++    enumFromTo n m = case m `infDiff` n of++        Right _ -> []+        Left k  -> f k n  where++            f Zero     l  = [l]+            f (Succ j) l  = l: f j (Succ l)+            f Inf      l  = iterate Succ l+    +    enumFromThen n n' = case n `zeroDiff` n' of++        -- constant sequence+        Left Zero -> n: repeat n'++        -- decreasing sequence+        Left d -> n: n': f (n' `zeroDiff` d) where++            f (Right _)               = []+            f (Left j)                = j: f (j `zeroDiff` d)++        -- increasing sequence+        Right d  -> n: iterate (d +) n'+++    enumFromThenTo n n' m = case n `zeroDiff` n' of     -- [n, n' .. m]++        -- constant sequence+        Left Zero -> n: repeat n'++        -- decreasing sequence+        Left d -> case m `zeroDiff` n of++            Left Zero -> [n]+            Left _    -> []+            Right k   -> n: f (n' `zeroDiff` m) n'  where    -- n' >= m ?    n'-m = (-(m-n)) - (n-n'),  if n,m < inf++                f (Right _) _                 = []+                f (Left j)  l                 = l: f (j `zeroDiff` d) (l - d)++        -- increasing sequence+        Right d  -> case m `infDiff` n of++            Right _ -> []+            Left k  -> n: f (k `infDiff` d) n'  where++                f (Right _)   _  = []+                f (Left j)    l  = l: f (j `infDiff` d) (d + l)++     fromEnum n = f 0 n where          f i Zero = i         f i (Succ m) = i' `seq` f i' m  where i' = i+1+        f _ Inf = error "Number.Peano.Inf: fromEnum infinity." + instance Real Nat where      toRational n = fromIntegral n % 1  instance Integral Nat where -    toInteger n = f 0 n where+    toInteger n = case toInteger' n of+        Just i  -> i+        Nothing -> error "Number.Peano.Inf: toInteger infinity." -        f i Zero = i-        f i (Succ m) = i' `seq` f i' m  where i' = i+1+    quotRem _ _ = error "Number.Peano.Inf: quotRem not implemented." -    quotRem _ _ = error "Nat: quotRem not implemented."+instance Bounded Nat where++    minBound = Zero+    maxBound = Inf+ 

@@ -1,5 +1,5 @@ name:           peano-inf-version:        0.1+version:        0.2 synopsis:       Lazy Peano numbers including observable infinity value. description:         Lazy Peano numbers including observable infinity value.@@ -7,7 +7,7 @@     This data type was needed in a graph traversing algorithm.     .     This data type is ideal for lazy list length computation (the infinite value is not needed in this case).-    See also <http://people.inf.elte.hu/divip/peano/>+    For a comparison with other Peano number implementation, see <http://people.inf.elte.hu/divip/peano/> category:       Data author:         Péter Diviánszky <divip@aszt.inf.elte.hu> maintainer:     Péter Diviánszky <divip@aszt.inf.elte.hu>