Source file: exclusive-scan.fut

Exclusive scan

There are two common ways of specifying scans: inclusive and exclusive. In an inclusive scan, element i of the output includes element i of the input, while for an exclusive scan it only goes up to i-1. The scan functon in Futhark is an inclusive scan, but an exclusive scan is provided as exscan. It is defined as follows:

def exscan [n] 'a (op: a -> a -> a) (ne: a) (as: [n]a) : *[n]a =
  scatter (replicate n ne)
          (map (+ 1) (0..1..<n))
          (scan op ne as)

It is sometimes useful to have both the inclusive and exclusive scan simultaneously, for example when the two are consumed together in a subsequent scatter. The following function computes both in a single pass, returning an array of pairs where the first component is the inclusive scan and the second is the exclusive scan:

import "no-neutral-element"

def exclusive_op 't (op: t -> t -> t) (a1: t, _: t) (a2: t, b2: t) : (t, t) =
  (a1 `op` a2, a1 `op` b2)

def incexscan [n] 't (op: t -> t -> t) (ne: t) (xs: [n]t) : [n](t, t) =
  map (\x -> #val (x, ne)) xs
  |> scan (f_with_neutral (exclusive_op op)) #neutral
  |> map (\t ->
            match t
            case #neutral -> (ne, ne)
            case (#val r) -> r)

This avoids the scatter at the cost of a more complex operator passed to scan, and it allows the compiler to fuse the scan with a subsequent consumer of either component.

Exclusive scan

See also