Gather and scatter
In vector programming, gather is an operation that takes a source
array xs and an array of indexes is, and for each i in is
produces the value xs[i]. Futhark does not have a dedicated
gather function, but we can use a combination of map and array
indexing to write our own.
def gather 'a (xs: []a) (is: []i32) =
map (\i -> xs[i]) isScatter is an operation that writes (index,value)-pairs to some
destination array. This is a primitive in Futhark, scatter,
which is of type
val scatter 'a : (dest: *[]a) -> (is: []i32) -> (vs: []a) -> *[]aThe * before on the destination and return type is a uniqueness
annotation. We can ignore it if the destination array we pass to
scatter is always a fresh array created with replicate or
copy:
def xs = scatter (replicate 7 0) [0, 2, 4, 6] [1, 2, 3, 4]xs now has the value [1i32, 0i32, 2i32, 0i32, 3i32, 0i32, 4i32]. Of course, this particular value is better constructed
using just map and iota. For a real use of scatter, see the
radix sort example.
scatter ignores out-of-bounds writes. However, there is a risk
of writing multiple values to the same index. This is only allowed
if the same value is being written. For a related construct that
can handle duplicate writes in other ways, see
reduce_by_index.