peano-inf 0.6.1 → 0.6.2

raw patch · 3 files changed

+46/−17 lines, 3 filesdep +containersPVP ok

version bump matches the API change (PVP)

Dependencies added: containers

API changes (from Hackage documentation)

Files

• Number/Peano/Inf.hs +5/−12
• Number/Peano/Inf/Functions.hs +36/−2
• peano-inf.cabal +5/−3

@@ -51,13 +51,12 @@     | Succ Nat     | Inf            +-- Serial instance needed for testing instance Serial Nat where     series = cons0 Zero \/ cons1 Succ \/ cons0 Inf  -{- | -Observable infinity value.--}+-- | Observable infinity value. infinity :: Nat infinity = Inf @@ -168,10 +167,7 @@ -} infixl 6 `infDiff` -infDiff-    :: Nat             -- ^ n-    -> Nat             -- ^ m-    -> Either Nat Nat  -- ^ n >= m: Left (n-m),  n < m: Right (m-n)+infDiff :: Nat -> Nat -> Either Nat Nat  Inf    `infDiff` _      = Left Inf Succ n `infDiff` Succ m = n `infDiff` m@@ -194,10 +190,7 @@ -} infixl 6 `zeroDiff` -zeroDiff-    :: Nat             -- ^ n-    -> Nat             -- ^ m-    -> Either Nat Nat  -- ^ n >= m: Left (n-m),  n < m: Right (m-n)+zeroDiff :: Nat -> Nat -> Either Nat Nat  n      `zeroDiff` Zero   = Left  n  Zero   `zeroDiff` m      = Right m@@ -258,7 +251,7 @@         f i (Succ m) = i' `seq` f i' m  where i' = i+1         f _ Inf = error "Number.Peano.Inf: fromEnum infinity." -    enumFrom n = enumFromTo n Inf+    enumFrom = iterate Succ      {- |             @[inf.. inf] == [inf, inf, inf, ..@

@@ -2,11 +2,14 @@     ( minimum     , maximum     , length+    , nodeRank     ) where  import Number.Peano.Inf -import qualified Prelude as P+import qualified Data.Set as Set++import qualified Prelude import Prelude hiding (minimum, maximum, length)  {- |@@ -34,11 +37,42 @@  > length (undefined: undefined) >= 1 -}- length :: [a] -> Nat length [] = 0 length (_:t) = succ (length t) +{- | +Rank computation with lazy Peano numbers. +The dependence function represents a graph with multiedges (edges with multiple start nodes).+@dependence n@ is the list of the start nodes of all multiedges whose end node is @n@.++@nodeRank n@ computes the length of the shortest path to @n@. Note that if @n@ is an end point of a multiedge with no start point,+then @nodeRank n == 0@.++* If @dependence n == []@ then @nodeRank n == infinity@, because @n@ is not accessable.++* If @any null (dependence n)@ then @nodeRank n == 0@++* Otherwise if @dependence n == [l1, l2, ..]@ then+    @nodeRank n == 1 + minimum [maximum (map nodeRank l1), maximum (map nodeRank l2), ..]@++If there is an inevitable cycle in the graph, the rank is @infinity@.+One can observe these cases, due to the observable infinity value.+-}+nodeRank +    :: Ord n                +    => (n -> [[n]])         -- ^ dependence function+    -> n                    -- ^ node+    -> Nat                  -- ^ rank of the node+nodeRank dependence node = rank Set.empty node  where++    rank visited node+        | Set.member node visited   = infinity+        | otherwise                 = minimum $ map f $ dependence node+     where+        visited' = Set.insert node visited++        f = maximum . map (succ . rank visited')  

@@ -1,11 +1,12 @@ name:           peano-inf-version:        0.6.1+version:        0.6.2 synopsis:       Lazy Peano numbers including observable infinity value. description:         Lazy Peano numbers including observable infinity value.     .-    This data type is ideal for lazy list length computation (the infinite value is not needed in this case).-    For a comparison with other Peano number implementation, see <http://people.inf.elte.hu/divip/peano/>+    This data type is ideal for lazy list length computation and for serveral graph algroithms.+    .+    For a comparison with other Peano number implementations, 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>@@ -20,6 +21,7 @@     ghc-options:    -Wall -fno-warn-overlapping-patterns -fno-warn-incomplete-patterns     build-depends:         base,+        containers,         lazysmallcheck      exposed-modules: