peano-inf 0.6.2 → 0.6.5

raw patch · 2 files changed

+74/−10 lines, 2 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• Number/Peano/Inf/Functions.hs +72/−8
• peano-inf.cabal +2/−2

@@ -3,6 +3,9 @@     , maximum     , length     , nodeRank+--    , nodeRankSimple +    , nodeRankMemo+    , nodeRankMemoIntegral     ) where  import Number.Peano.Inf@@ -41,6 +44,19 @@ length [] = 0 length (_:t) = succ (length t) ++nodeRankSimple +    :: (n -> [[n]]) +    -> n +    -> Nat++nodeRankSimple dependence = rank where++    rank = minimum . map f . dependence++    f = maximum . map (succ . rank)++ {- |  Rank computation with lazy Peano numbers. @@ -50,23 +66,20 @@ @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@+* 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), ..]@+* Otherwise @nodeRank n == 1 + minimum [maximum (map nodeRank l1), maximum (map nodeRank l2), ..] where @[l1, l2, ..] == dependence n@ if this is computable.@ -If there is an inevitable cycle in the graph, the rank is @infinity@.-One can observe these cases, due to the observable infinity value.+* Otherwise the rank is @infinity@. (These cases are observable.) -} nodeRank      :: Ord n                     => (n -> [[n]])         -- ^ dependence function     -> n                    -- ^ node     -> Nat                  -- ^ rank of the node-nodeRank dependence node = rank Set.empty node  where +nodeRank dependence = rank Set.empty  where+     rank visited node         | Set.member node visited   = infinity         | otherwise                 = minimum $ map f $ dependence node@@ -74,5 +87,56 @@         visited' = Set.insert node visited          f = maximum . map (succ . rank visited')+++{- | +Memoising version of @nodeRank@.++The rank of inaccessable nodes are @inductive_infinity@.+These cases are observable with the predicate @(> n)@ where @n@ is an upper bound for the number of nodes in the graph.+-}+nodeRankMemo+    :: (n -> [[n]])         -- ^ dependence function+    -> (n -> Nat)           -- ^ memoised version of the result function+    -> (n -> Nat)           -- ^ rank of a node++nodeRankMemo dependence rank' = rank  where++    rank = minimum . map f . dependence++    f = maximum . map (succ . rank')++{- | +@nodeRankMemo@ specialised for integral types.+-}+nodeRankMemoIntegral+    :: Integral a+    => (a -> [[a]])         -- ^ dependence function+    -> a                    -- ^ node number+    -> Nat                  -- ^ rank of the node++nodeRankMemoIntegral dep = f where ++    f = nodeRankMemo dep (memoise f)++----------------- memoisation for non-negative integrals++data T x = B x (T x) (T x)++memoise :: Integral a => (a -> x) -> (a -> x)+memoise = decode . code+ where+	code f = B (f 0) (code (\n -> f (2*n+1)))+		             (code (\n -> f (2*n+2)))++	decode (B x l r) n +		| n == 0    = x+		| odd n     = decode l (n `div` 2)+		| otherwise = decode r ((n-2) `div` 2)++-----------------+++  

@@ -1,10 +1,10 @@ name:           peano-inf-version:        0.6.2+version:        0.6.5 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 and for serveral graph algroithms.+    This data type is ideal for lazy list length computation and for serveral graph algorithms.     .     For a comparison with other Peano number implementations, see <http://people.inf.elte.hu/divip/peano/> category:       Data