peano-inf (empty) → 0.1
raw patch · 4 files changed
+207/−0 lines, 4 filesdep +basesetup-changed
Dependencies added: base
Files
- LICENSE +31/−0
- Number/Peano/Inf.hs +142/−0
- Setup.hs +5/−0
- peano-inf.cabal +29/−0
+ LICENSE view
@@ -0,0 +1,31 @@+Copyright Péter Diviánszky 2008++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++ * Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer.++ * Redistributions in binary form must reproduce the above+ copyright notice, this list of conditions and the following+ disclaimer in the documentation and/or other materials provided+ with the distribution.++ * Neither the name of Péter Diviánszky nor the names of other+ contributors may be used to endorse or promote products derived+ from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.+
+ Number/Peano/Inf.hs view
@@ -0,0 +1,142 @@+{- |+Copyright : (c) Peter Divianszky 2008+Maintainer : divip@aszt.inf.elte.hu+Stability : experimental+Portability : portable++Lazy Peano numbers including observable infinity value.+-}+module Number.Peano.Inf+ ( Nat (Zero, Succ)+ , infinity+ , isInfinity+ , (-|)+ ) where++import Data.Ratio ((%))++-- | Natural numbers and infinity.+data Nat+ = Zero+ | Succ Nat+ | Inf ++-- | Observable infinity value.++infinity :: Nat+infinity = Inf++-- | True for @(infinity)@, @(5 + 4 * infinity)@ etc. Evaluates to bottom for @(genericLength [1..])@.++isInfinity :: Nat -> Bool+isInfinity Zero = False+isInfinity Inf = True+isInfinity (Succ n) = isInfinity n++instance Eq Nat where++ Zero == Zero = True+ Succ n == Succ m = n == m+ Inf == Inf = error "Nat: infinity == infinity"+ Succ n == Inf = n == Inf + Inf == Succ m = Inf == m + _ == _ = False++instance Ord Nat where++ Zero `compare` Zero = EQ+ Zero `compare` _ = LT+ _ `compare` Zero = GT+ Succ n `compare` Succ m = n `compare` m+ Inf `compare` Inf = error "Nat: 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 < Succ m = Inf < m+ Succ n < Inf = n < Inf++ x > y = y < x++ x <= y = not (y < x)++ x >= y = not (x < y)++ Zero `max` x = x+ x `max` Zero = x+ Succ n `max` Succ m = Succ (n `max` m)+ _ `max` _ = Inf++ Zero `min` _ = Zero+ _ `min` Zero = Zero+ Succ n `min` Succ m = Succ (n `min` m)+ Inf `min` m = m+ n `min` Inf = n++instance Show Nat where++ show Inf = "infinity"+ show x = show $ toInteger x++-- | Subtraction maximized to 0. 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+++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"++ Zero + m = m+ Succ n + m = Succ (n + m)+ Inf + _ = Inf++ Succ n * m = m + n * m+ Zero * _ = Zero+ Inf * _ = Inf++ fromInteger i | i < 0 = error "Nat: fromInteger on negative value."+ fromInteger i = iterate Succ Zero !! fromInteger i++ abs x = x++ signum Zero = Zero+ signum _ = Succ Zero++instance Enum Nat where++ toEnum i | i < 0 = error "Nat: toEnum on negative value."+ toEnum i = iterate Succ Zero !! i++ fromEnum n = f 0 n where++ f i Zero = i+ f i (Succ m) = i' `seq` f i' m where i' = i+1++instance Real Nat where++ toRational n = fromIntegral n % 1++instance Integral Nat where++ toInteger n = f 0 n where++ f i Zero = i+ f i (Succ m) = i' `seq` f i' m where i' = i+1++ quotRem _ _ = error "Nat: quotRem not implemented."+
+ Setup.hs view
@@ -0,0 +1,5 @@++import Distribution.Simple++main = defaultMain+
+ peano-inf.cabal view
@@ -0,0 +1,29 @@+name: peano-inf+version: 0.1+synopsis: Lazy Peano numbers including observable infinity value.+description: + Lazy Peano numbers including observable infinity value.+ .+ 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/>+category: Data+author: Péter Diviánszky <divip@aszt.inf.elte.hu>+maintainer: Péter Diviánszky <divip@aszt.inf.elte.hu>+copyright: (c) 2008 by Péter Diviánszky+license: BSD3+license-file: LICENSE+stability: experimental+build-type: Simple+cabal-version: >=1.2++library+ ghc-options: -Wall -fno-warn-overlapping-patterns -fno-warn-incomplete-patterns+ build-depends:+ base++ exposed-modules:+ Number.Peano.Inf++