# Functions for Array Manipulation

## 14.09.2020

This is a list of array functions present in the functional programming language Futhark.

## Map

$map$ is the typical map found in functional programming languages. It has the type signature $$map : (\alpha \rightarrow \beta) \rightarrow [\alpha] \rightarrow [\beta]$$ For an array of elements of type $\alpha$ it produces an array of elements of type $\beta$ by applying the function given as the first argument, to each of the elements of $[\alpha]$.

## Map2

$map2$ receives a binary function, $f$, and two arrays, $a,b$, as input. the return value is an array obtained by applying to $f$ an element from both $a$ and $b$. It has the type signature: $$\textbf{map2} : (\alpha_1 \rightarrow \alpha_2 \rightarrow \beta ) \rightarrow [\alpha_1] \rightarrow [\alpha_2] \rightarrow [\beta]$$ It is given as $$\textbf{map2}\ f\ [ a_1 , \dots , a_n ]\ [ b_1 , \dots , b_n ] = [ f\ a_1\ b_1 , \dots , f\ a_n\ b_n ]$$

## Reduce

$reduce$ corresponds to fold found in functional programming languages. However we restrict the operator of fold to be binary and associative. And we restrict the accumulator to be the neutral element with respect to the underlying structure of reduced result. That is we have $$reduce : (\alpha \rightarrow \alpha \rightarrow \alpha) \rightarrow \alpha \rightarrow [\alpha] \rightarrow \alpha$$ This differs from fold in the sense that for fold we do not restrict the resulting type by the type of the input. fold has the type signature $$fold : ((\beta \rightarrow \alpha \rightarrow \beta) \rightarrow \beta \rightarrow [\alpha] \rightarrow \beta)$$ $reduce$ applies the operator given to each element of the input array in series. That is $$\textbf{reduce}\ \odot\ e\ [x_1, \dots , x_n ] = e \odot x_1 \odot \dots \odot x_n$$

## Zip

$zip$ is found in most functional programming languages. It takes two arrays and inject the elements into matching tuples in a resulting array. That is $$\textbf{zip} : [\alpha_1] \rightarrow [\alpha_2] \rightarrow [(\alpha_1,\alpha_2)]$$ given as $$\textbf{zip}\ [a_1 , \dots , a_n]\ [b_1 , \dots , b_n] = [(a_1,b_1), \dots , (a_n,b_n)]$$ The input arrays should have same length.

## Unzip

$unzip$ is the projection version of $zip$ it projects each tuple of an array into elements of two new arrays. The type signature is $$\textbf{unzip} : [(\alpha_1,\alpha_2)] \rightarrow ([\alpha_1],[\alpha_2])$$

## Scan

$scan$ is a function that takes as input an operator, $\oplus$, and an array and returns an array in which elements are applied by $\oplus$ up till that element. The type signature is $$\textbf{scan} : (\alpha \rightarrow \alpha \rightarrow \alpha) \rightarrow \alpha \rightarrow [\alpha] \rightarrow [\alpha]$$ and it is given as $$\textbf{scan}\ \oplus\ e_{\oplus}\ [a_1 , \dots , a_n] = [a_1,a_1 \oplus a_2 , \dots , a_1 \oplus \dots \oplus a_n]$$

## Scan - Exclusive

An exclusive scan is the same as a normal scan, but with the identity element placed in the first slot of the resulting array. This is given as $$\textbf{scan}\ \oplus\ e_{\oplus}\ [a_1 , \dots , a_n] = [e_{\oplus}, a_1,a_1 \oplus a_2 , \dots , a_1 \oplus \dots \oplus a_{n - 1}]$$

## Segmented Scan

A segmented scan works on a two dimensional array. Each element is an array that a scan is performed on. That is $$\textbf{sgmScan}\ \oplus\ e_{\oplus}\ [[a_1, \dots],[b_1, \dots], \dots] = [\textbf{scan}\ \oplus\ e_{\oplus}\ [a_1, \dots],\textbf{scan}\ \oplus\ e_{\oplus}\ [b_1,\dots],\dots]$$ This is the same as mapping $scan$ into a two dimensional array.

...

## Constructers - Iota

$iota$ given some input integer $n$ creates an array of size $n$ with elements from $0 \dots n - 1$. The type signature is $$\textbf{iota} : Int \rightarrow [Int]$$ given as $$\textbf{iota}\ n = [0 , \dots , n - 1]$$

## Replicate

$replicate$ given some intput integer $n$ and some element $a$ creates an array of length $n$ with element $a$. The type signature $$\textbf{replicate} : Int \rightarrow \alpha \rightarrow [\alpha]$$ and it is given as $$\textbf{replicate}\ n\ a\ = [a, \dots , a]$$

## Scatter

$scatter$ has the following type signature $$\textbf{scatter} : [\alpha] \rightarrow [Int] \rightarrow [\alpha] \rightarrow [\alpha]$$ Given some input array $x$ and and index array $i$ and an dataarray $y$ it scatters the elements of $y$ into $x$ according to the indices of $i$. $x$ is updated in place, that is the non-functional way of doing it. Given the following we can illustrate scatter $$x = [a_0,a_1,a_2]$$ and $$i = [1,-1]$$ and $$y = [b_0,b_1]$$ now $$\textbf{scatter}\ x\ i\ y = [a_0,b_0,a_2]$$ out of bound indices are ignored.