scan(f, init, xs, length=None, reverse=False, unroll=1)¶
Scan a function over leading array axes while carrying along state.
The type signature in brief is
scan :: (c -> a -> (c, b)) -> c -> [a] -> (c, [b])
where we use [t] here to denote the type t with an additional leading axis. That is, if t is an array type then [t] represents the type with an additional leading axis, and if t is a pytree (container) type with array leaves then [t] represents the type with the same pytree structure and corresponding leaves each with an additional leading axis.
ais an array type or None, and
bis an array type, the semantics of
scanare given roughly by this Python implementation:
def scan(f, init, xs, length=None): if xs is None: xs = [None] * length carry = init ys =  for x in xs: carry, y = f(carry, x) ys.append(y) return carry, np.stack(ys)
Unlike that Python version, both
bmay be arbitrary pytree types, and so multiple arrays can be scanned over at once and produce multiple output arrays. (None is actually an empty pytree.)
Also unlike that Python version,
scanis a JAX primitive and is lowered to a single XLA While HLO. That makes it useful for reducing compilation times for jit-compiled functions, since native Python loop constructs in an
@jitfunction are unrolled, leading to large XLA computations.
Finally, the loop-carried value
carrymust hold a fixed shape and dtype across all iterations (and not just be consistent up to NumPy rank/shape broadcasting and dtype promotion rules, for example). In other words, the type
cin the type signature above represents an array with a fixed shape and dtype (or a nested tuple/list/dict container data structure with a fixed structure and arrays with fixed shape and dtype at the leaves).
f – a Python function to be scanned of type
c -> a -> (c, b), meaning that
faccepts two arguments where the first is a value of the loop carry and the second is a slice of
xsalong its leading axis, and that
freturns a pair where the first element represents a new value for the loop carry and the second represents a slice of the output.
init – an initial loop carry value of type
c, which can be a scalar, array, or any pytree (nested Python tuple/list/dict) thereof, representing the initial loop carry value. This value must have the same structure as the first element of the pair returned by
xs – the value of type
[a]over which to scan along the leading axis, where
[a]can be an array or any pytree (nested Python tuple/list/dict) thereof with consistent leading axis sizes.
length – optional integer specifying the number of loop iterations, which must agree with the sizes of leading axes of the arrays in
xs(but can be used to perform scans where no input
reverse – optional boolean specifying whether to run the scan iteration forward (the default) or in reverse, equivalent to reversing the leading axes of the arrays in both
unroll – optional positive int specifying, in the underlying operation of the scan primitive, how many scan iterations to unroll within a single iteration of a loop.
A pair of type
(c, [b])where the first element represents the final loop carry value and the second element represents the stacked outputs of the second output of
fwhen scanned over the leading axis of the inputs.