ad 1.1.1 → 1.1.3

raw patch · 2 files changed

+26/−5 lines, 2 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Numeric/AD/Internal/Reverse.hs +19/−4
• ad.cabal +7/−1

@@ -40,11 +40,13 @@ import Control.Applicative (Applicative(..),(<$>)) import Control.Monad.ST import Control.Monad (forM_)-import Data.List (foldl')+import Data.List (foldl', delete) import Data.Array.ST import Data.Array-import Data.IntMap (IntMap, fromListWith, findWithDefault)-import Data.Graph (graphFromEdges', topSort, Vertex)+import Data.IntMap (IntMap, fromListWith, findWithDefault, fromAscList, +                    updateLookupWithKey)+import qualified Data.IntSet as IS+import Data.Graph (graphFromEdges', Vertex, vertices, edges, transposeG, Graph) import Data.Reify (reifyGraph, MuRef(..)) import qualified Data.Reify.Graph as Reified import Data.Traversable (Traversable, mapM)@@ -148,6 +150,19 @@          -- this isn't _quite_ right, as it should allow negative zeros to multiply through +topSortAcyclic :: Graph -> [Vertex]+topSortAcyclic g = go (fromAscList . assocs $ transposeG g) starters+  where starters = IS.toList $ foldl' (flip IS.delete)+                                      (IS.fromList $ vertices g)+                                      (map snd $ edges g)+        go _ [] = []+        go g' (n:ns) = let (g'',ns') = foldl' (uncurry (prune n)) (g',[]) (g!n)+                       in n : go g'' (ns'++ns)+        prune n g' acc m = let f _ = Just . delete n+                               (Just ns, g'') = updateLookupWithKey f m g'+                           in g'' `seq` (g'', if null (tail ns) then m:acc else acc)++ -- | This returns a list of contributions to the partials. -- The variable ids returned in the list are likely /not/ unique! partials :: Num a => AD Reverse a -> [(Int, a)]@@ -158,7 +173,7 @@         sensitivities = runSTArray $ do             ss <- newArray (sbounds xs) 0             writeArray ss start 1-            forM_ (topSort g) $+            forM_ (topSortAcyclic g) $                 backPropagate vmap ss             return ss         sbounds ((a,_):as) = foldl' (\(lo,hi) (b,_) -> let lo' = min lo b; hi' = max hi b in lo' `seq` hi' `seq` (lo', hi')) (a,a) as

@@ -1,5 +1,5 @@ name:         ad-version:      1.1.1+version:      1.1.3 license:      BSD3 license-File: LICENSE copyright:    (c) Edward Kmett 2010-2011,@@ -59,6 +59,12 @@     * @T@ means the result is transposed with respect to the traditional formulation.     .     * @0@ means that the resulting derivative list is padded with 0s at the end.+    .+    Changes since 1.1.0+    .+    * Introduced a much faster topological sort into the reverse mode AD implementation by Anthony Cowley. This fixes a space leak and a stack overflow problem on very large (>2000 variable) problem sets.+    .+    * Made bound calculations in reverse mode more strict.     .     Changes since 1.0.0     .