Fix backpropagation error in Kahn mode

ekmett / ad

Automatic Differentiation

http://hackage.haskell.org/package/ad

BSD 3-Clause "New" or "Revised" License

368 stars 73 forks source link

Fix backpropagation error in Kahn mode #84

Closed msakai closed 4 years ago

msakai commented 4 years ago

If there are duplicates in successors, topSortAcyclic may produce duplicated nodes that end up duplicated backpropagation.

For example:

> import qualified Numeric.AD.Mode.Reverse as Reverse
> import qualified Numeric.AD.Mode.Kahn as Kahn
> f x = sq (x + 1) where sq x = x * x
> Reverse.diff f 1.0
4.0
> Kahn.diff f 1.0
8.0

cartazio commented 4 years ago

this seems (naively) like a good bug catch!

1) should we add a test? 2) otherwise seems fine to me (though i would challenge you to keep the function in question generic, since that polymorphic functions avoid more bugs :) , you could eg make it forall n . Eq n => ... )

@ekmett @RyanGlScott thoughts?