Numeric.AD.Internal.Kahn

This module provides reverse-mode Automatic Differentiation implementation using linear time topological sorting after the fact.

For this form of reverse-mode AD we use StableName to recover sharing information from the tape to avoid combinatorial explosion, and thus run asymptotically faster than it could without such sharing information, but the use of side-effects contained herein is benign.

Documentation

newtype Kahn a

Kahn is a Mode using reverse-mode automatic differentiation that provides fast diffFU, diff2FU, grad, grad2 and a fast jacobian when you have a significantly smaller number of outputs than inputs.

Constructors

Kahn (Tape a (Kahn a))

Instances

(Num a, Bounded a) => Bounded (Kahn a)

Methods

minBound :: Kahn a

maxBound :: Kahn a

(Num a, Enum a) => Enum (Kahn a)

Methods

succ :: Kahn a -> Kahn a

pred :: Kahn a -> Kahn a

toEnum :: Int -> Kahn a

fromEnum :: Kahn a -> Int

enumFrom :: Kahn a -> [Kahn a]

enumFromThen :: Kahn a -> Kahn a -> [Kahn a]

enumFromTo :: Kahn a -> Kahn a -> [Kahn a]

enumFromThenTo :: Kahn a -> Kahn a -> Kahn a -> [Kahn a]

(Num a, Eq a) => Eq (Kahn a)

Methods

(==) :: Kahn a -> Kahn a -> Bool

(/=) :: Kahn a -> Kahn a -> Bool

Floating a => Floating (Kahn a)

Methods

pi :: Kahn a

exp :: Kahn a -> Kahn a

log :: Kahn a -> Kahn a

sqrt :: Kahn a -> Kahn a

(**) :: Kahn a -> Kahn a -> Kahn a

logBase :: Kahn a -> Kahn a -> Kahn a

sin :: Kahn a -> Kahn a

cos :: Kahn a -> Kahn a

tan :: Kahn a -> Kahn a

asin :: Kahn a -> Kahn a

acos :: Kahn a -> Kahn a

atan :: Kahn a -> Kahn a

sinh :: Kahn a -> Kahn a

cosh :: Kahn a -> Kahn a

tanh :: Kahn a -> Kahn a

asinh :: Kahn a -> Kahn a

acosh :: Kahn a -> Kahn a

atanh :: Kahn a -> Kahn a

log1p :: Kahn a -> Kahn a

expm1 :: Kahn a -> Kahn a

log1pexp :: Kahn a -> Kahn a

log1mexp :: Kahn a -> Kahn a

Fractional a => Fractional (Kahn a)

Methods

(/) :: Kahn a -> Kahn a -> Kahn a

recip :: Kahn a -> Kahn a

fromRational :: Rational -> Kahn a

Num a => Num (Kahn a)

Methods

(+) :: Kahn a -> Kahn a -> Kahn a

(-) :: Kahn a -> Kahn a -> Kahn a

(*) :: Kahn a -> Kahn a -> Kahn a

negate :: Kahn a -> Kahn a

abs :: Kahn a -> Kahn a

signum :: Kahn a -> Kahn a

fromInteger :: Integer -> Kahn a

(Num a, Ord a) => Ord (Kahn a)

Methods

compare :: Kahn a -> Kahn a -> Ordering

(<) :: Kahn a -> Kahn a -> Bool

(<=) :: Kahn a -> Kahn a -> Bool

(>) :: Kahn a -> Kahn a -> Bool

(>=) :: Kahn a -> Kahn a -> Bool

max :: Kahn a -> Kahn a -> Kahn a

min :: Kahn a -> Kahn a -> Kahn a

Real a => Real (Kahn a)

Methods

toRational :: Kahn a -> Rational

RealFloat a => RealFloat (Kahn a)

Methods

floatRadix :: Kahn a -> Integer

floatDigits :: Kahn a -> Int

floatRange :: Kahn a -> (Int, Int)

decodeFloat :: Kahn a -> (Integer, Int)

encodeFloat :: Integer -> Int -> Kahn a

exponent :: Kahn a -> Int

significand :: Kahn a -> Kahn a

scaleFloat :: Int -> Kahn a -> Kahn a

isNaN :: Kahn a -> Bool

isInfinite :: Kahn a -> Bool

isDenormalized :: Kahn a -> Bool

isNegativeZero :: Kahn a -> Bool

isIEEE :: Kahn a -> Bool

atan2 :: Kahn a -> Kahn a -> Kahn a

RealFrac a => RealFrac (Kahn a)

Methods

properFraction :: Integral b => Kahn a -> (b, Kahn a)

truncate :: Integral b => Kahn a -> b

round :: Integral b => Kahn a -> b

ceiling :: Integral b => Kahn a -> b

floor :: Integral b => Kahn a -> b

Show a => Show (Kahn a)

Methods

showsPrec :: Int -> Kahn a -> ShowS

show :: Kahn a -> String

showList :: [Kahn a] -> ShowS

MuRef (Kahn a)

Associated Types

type DeRef (Kahn a) :: * -> *

Methods

mapDeRef :: Applicative f => (forall b. (MuRef b, ((* -> *) ~ DeRef (Kahn a)) (DeRef b)) => b -> f u) -> Kahn a -> f (DeRef (Kahn a) u)

Erf a => Erf (Kahn a)

Methods

erf :: Kahn a -> Kahn a

erfc :: Kahn a -> Kahn a

erfcx :: Kahn a -> Kahn a

normcdf :: Kahn a -> Kahn a

InvErf a => InvErf (Kahn a)

Methods

inverf :: Kahn a -> Kahn a

inverfc :: Kahn a -> Kahn a

invnormcdf :: Kahn a -> Kahn a

Num a => Mode (Kahn a)

Associated Types

type Scalar (Kahn a) :: *

Methods

isKnownConstant :: Kahn a -> Bool

isKnownZero :: Kahn a -> Bool

auto :: Scalar (Kahn a) -> Kahn a

(*^) :: Scalar (Kahn a) -> Kahn a -> Kahn a

(^*) :: Kahn a -> Scalar (Kahn a) -> Kahn a

(^/) :: Kahn a -> Scalar (Kahn a) -> Kahn a

zero :: Kahn a

Num a => Jacobian (Kahn a)

Associated Types

type D (Kahn a) :: *

Methods

unary :: (Scalar (Kahn a) -> Scalar (Kahn a)) -> D (Kahn a) -> Kahn a -> Kahn a

lift1 :: (Scalar (Kahn a) -> Scalar (Kahn a)) -> (D (Kahn a) -> D (Kahn a)) -> Kahn a -> Kahn a

lift1_ :: (Scalar (Kahn a) -> Scalar (Kahn a)) -> (D (Kahn a) -> D (Kahn a) -> D (Kahn a)) -> Kahn a -> Kahn a

binary :: (Scalar (Kahn a) -> Scalar (Kahn a) -> Scalar (Kahn a)) -> D (Kahn a) -> D (Kahn a) -> Kahn a -> Kahn a -> Kahn a

lift2 :: (Scalar (Kahn a) -> Scalar (Kahn a) -> Scalar (Kahn a)) -> (D (Kahn a) -> D (Kahn a) -> (D (Kahn a), D (Kahn a))) -> Kahn a -> Kahn a -> Kahn a

lift2_ :: (Scalar (Kahn a) -> Scalar (Kahn a) -> Scalar (Kahn a)) -> (D (Kahn a) -> D (Kahn a) -> D (Kahn a) -> (D (Kahn a), D (Kahn a))) -> Kahn a -> Kahn a -> Kahn a

Num a => Grad (Kahn a) [a] (a, [a]) a

Methods

pack :: Kahn a -> [Kahn a] -> Kahn a

unpack :: ([a] -> [a]) -> [a]

unpack' :: ([a] -> (a, [a])) -> (a, [a])

Grad i o o' a => Grad (Kahn a -> i) (a -> o) (a -> o') a

Methods

pack :: (Kahn a -> i) -> [Kahn a] -> Kahn a

unpack :: ([a] -> [a]) -> a -> o

unpack' :: ([a] -> (a, [a])) -> a -> o'

type DeRef (Kahn a)

type DeRef (Kahn a) = Tape a

type Scalar (Kahn a)

type Scalar (Kahn a) = a

type D (Kahn a)

type D (Kahn a) = Id a

data Tape a t

A Tape records the information needed back propagate from the output to each input during reverse Mode AD.

Constructors

Zero

Lift !a

Var !a !Int

Binary !a a a t t

Unary !a a t

Instances

(Data a, Data t) => Data (Tape a t)

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Tape a t -> c (Tape a t)

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Tape a t)

toConstr :: Tape a t -> Constr

dataTypeOf :: Tape a t -> DataType

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c (Tape a t))

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Tape a t))

gmapT :: (forall b. Data b => b -> b) -> Tape a t -> Tape a t

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Tape a t -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Tape a t -> r

gmapQ :: (forall d. Data d => d -> u) -> Tape a t -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> Tape a t -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Tape a t -> m (Tape a t)

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Tape a t -> m (Tape a t)

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Tape a t -> m (Tape a t)

(Show a, Show t) => Show (Tape a t)

Methods

showsPrec :: Int -> Tape a t -> ShowS

show :: Tape a t -> String

showList :: [Tape a t] -> ShowS

partials :: forall a. Num a => Kahn a -> [(Int, a)]

This returns a list of contributions to the partials. The variable ids returned in the list are likely not unique!

partialArray :: Num a => (Int, Int) -> Kahn a -> Array Int a

Return an Array of partials given bounds for the variable IDs.

partialMap :: Num a => Kahn a -> IntMap a

Return an IntMap of sparse partials

derivative :: Num a => Kahn a -> a

derivative' :: Num a => Kahn a -> (a, a)

vgrad :: Grad i o o' a => i -> o

vgrad' :: Grad i o o' a => i -> o'

class Num a => Grad i o o' a | i -> a o o', o -> a i o', o' -> a i o where

Minimal complete definition

pack, unpack, unpack'

Methods

pack :: i -> [Kahn a] -> Kahn a

unpack :: ([a] -> [a]) -> o

unpack' :: ([a] -> (a, [a])) -> o'

Instances

Num a => Grad (Kahn a) [a] (a, [a]) a

Methods

pack :: Kahn a -> [Kahn a] -> Kahn a

unpack :: ([a] -> [a]) -> [a]

unpack' :: ([a] -> (a, [a])) -> (a, [a])

Grad i o o' a => Grad (Kahn a -> i) (a -> o) (a -> o') a

Methods

pack :: (Kahn a -> i) -> [Kahn a] -> Kahn a

unpack :: ([a] -> [a]) -> a -> o

unpack' :: ([a] -> (a, [a])) -> a -> o'

bind :: Traversable f => f a -> (f (Kahn a), (Int, Int))

unbind :: Functor f => f (Kahn a) -> Array Int a -> f a

unbindMap :: (Functor f, Num a) => f (Kahn a) -> IntMap a -> f a

unbindWith :: (Functor f, Num a) => (a -> b -> c) -> f (Kahn a) -> Array Int b -> f c

unbindMapWithDefault :: (Functor f, Num a) => b -> (a -> b -> c) -> f (Kahn a) -> IntMap b -> f c

primal :: Num a => Kahn a -> a

var :: a -> Int -> Kahn a

varId :: Kahn a -> Int