Although the name Vector is borrowed from <ForSyDe-Atom.html#reekie95 [Reekie95]> since it is more suggestive in the context of process networks, the Vector type is in fact modeling an infinite list defined as a category in [Skillicorn05]. According to this definition it should be implemented as following:

data Vector a = Null                   -- null element
              | Unit a                 -- singleton vector
              | Vector a <++> Vector a -- concatenate two vectors

This construction suggests the possibility of splitting a Vector into multiple parts and evaluating it in parallel. For simplicity and to ensure that the structure is flat and homogeneous, Vector is implemented using the same constructors as a regular Haskell list (see below). When defining skeletons of vectors we will not use the real constructors though, but the theoretical ones defined above and provided as functions. This way we align ForSyDe-Atom's Vector type with the skeleton theory and its theorems.

Another particularity of Vector is that it instantiates the reduction atom =\= as a right fold, as it is the most efficient lazy implementation of lists. As a consequence reduction is performed from right to left. This is noticed especially in the case of pipeline-based skeletons (see definition of pipe as a reduction with the right-associative composition operator .) is performed from right to left. Thus for reduce-based skeletons (e.g. prefix, suffix, recur, cascade, mesh) the result vectors shall be read from end to beginning.

Constructs a null vector.

>>> null
<>

Constructs a singleton vector.

>>> unit 1
<1>

Constructs a vector by appending two existing vectors.

>>> unit 1 <++> unit 2
<1,2>

Converts a list to a vector.

Converts a vector to a list.

Creates the infinite vector:

<1,2,3,4,...>

Used mainly for operation on indexes.

Returns True if the argument is a null vector.

Appends an element at the end of a vector.

farm is simply the Vector instance of the skeletom farm pattern (see farm22). If the function taken as argument is a process, then it creates a farm network of data parallel processes.

Constructors: farm[1-4][1-4].

>>> let v1 = vector [1,2,3,4,5]
>>> S.farm21 (+) v1 v1
<2,4,6,8,10>
>>> let s1 = SY.signal [1,2,3,4,5]
>>> let v2 = vector [s1,s1,s1]
>>> S.farm11 (comb11 (+1)) v2
<{2,3,4,5,6},{2,3,4,5,6},{2,3,4,5,6}>
>>> S.farm21 (\x -> comb11 (+x)) v1 v2
<{2,3,4,5,6},{3,4,5,6,7},{4,5,6,7,8}>

As the name suggests, it reduces a vector to an element based on an associative function. If the function is not associative, it can be treated like a pipeline.

Vector instantiates the skeletons for both reduce and reducei.

>>> let v1 = vector [1,2,3,4,5]
>>> S.reduce (+) v1
15
>>> let s1 = SY.signal [1,2,3,4,5]
>>> let s2 = SY.signal [10,10,10,10,10]
>>> let v2 = vector [s1,s1,s1]
>>> S.reduce (comb21 (+)) v2
{3,6,9,12,15}
>>> S.reducei (comb21 (+)) s2 v2
{13,16,19,22,25}

prefix peforms the parallel prefix operation on a vector. Equivalent process networks are constructed if processes are passed as arguments.

Similar to reduce and reducei, two versions prefix and prefixi are provided.

>>> let v1 = vector [1,2,3,4,5]
>>> prefix (+) v1
<15,14,12,9,5>
>>> let s1 = SY.signal [1,2,3,4,5]
>>> let s2 = SY.signal [10,10,10,10,10]
>>> let v2 = vector [s1,s1,s1]
>>> prefix (comb21 (+)) v2
<{3,6,9,12,15},{2,4,6,8,10},{1,2,3,4,5}>
>>> prefixi (comb21 (+)) s2 v2
<{13,16,19,22,25},{12,14,16,18,20},{11,12,13,14,15}>

suffix peforms the parallel suffix operation on a vector. Equivalent process networks are constructed if processes are passed as arguments.

Similar to reduce and reducei, two versions suffix and suffixi are provided.

>>> let v1 = vector [1,2,3,4,5]
>>> suffix (+) v1
<1,3,6,10,15>
>>> let s1 = SY.signal [1,2,3,4,5]
>>> let s2 = SY.signal [10,10,10,10,10]
>>> let v2 = vector [s1,s1,s1]
>>> suffix (comb21 (+)) v2
<{1,2,3,4,5},{2,4,6,8,10},{3,6,9,12,15}>
>>> suffixi (comb21 (+)) s2 v2
<{11,12,13,14,15},{12,14,16,18,20},{13,16,19,22,25}>

pipe creates a pipeline of functions from a vector. pipe simply instantiates the =<<= atom whereas pipeX instantiate their omologi from the ForSyDe.Atom.Skel module (see pipe2).

OBS: the pipelining is done in the order dictated by the function composition operator: from right to left.

Constructors: pipe[1-4].

>>> let v1 = vector [(+1),(+1),(+1)]
>>> S.pipe v1 1
4
>>> let s1 = SY.signal [1,2,3,4]
>>> let v2 = vector [1,2,3,4]
>>> S.pipe1 (\x -> comb11 (+x)) v2 s1
{11,12,13,14}

Infix operator for recur.

recur creates a systolic array from a vector of functions. Just like pipe and pipeX, there exists a raw recur version with an infix operator =/=, and the enhanced recurX which is meant for systematic partial application of a function on an arbitrary number of vectors until the desired vector of functions is obtained.

Constructors: (=/=), recur, recuri, recur[1-4][1-4].

>>> let v1 = vector [(+1),(+1),(+1)]
>>> recur v1 1
<4,3,2>
>>> recuri v1 1
<4,3,2,1>
>>> let s1 = SY.signal [1,2,3,4]
>>> let v2 = vector [1,2,3,4]
>>> recur1 (\x -> comb11 (+x)) v2 s1
<{11,12,13,14},{10,11,12,13},{8,9,10,11},{5,6,7,8}>

cascade creates a "cascading mesh" as a result of piping a vector into a vector of recur arrays.

Constructors: cascade, cascade[1-4].

>>> let v1 = vector [1,2,3,4]
>>> cascade (+) v1 v1
<238,119,49,14>
>>> let s1 = SY.signal [1,2,3,4]
>>> let vs = vector [s1, s1, s1]
>>> cascade (comb21 (+)) vs vs
<{20,40,60,80},{10,20,30,40},{4,8,12,16}>
>>> let vv = vector [vector [1,-1,1], vector [-1,1,-1], vector [1,-1,1] ]
>>> cascade1 (\x -> comb21 (\y z-> x*(y+z))) vv vs vs
<{16,32,48,64},{8,16,24,32},{-2,-4,-6,-8}>

mesh creates a 2D systolic array as a result of piping a vector into a vector of 1D systolic arrays.

Constructors: mesh, mesh[1-4].

>>> let v1 = vector [1,2,3,4]
>>> mesh (+) v1 v1
<<238,119,49,14>,<119,70,35,13>,<49,35,22,11>,<14,13,11,8>>
>>> let s1 = SY.signal [1,2,3,4]
>>> let vs = vector [s1, s1, s1]
>>> mesh (comb21 (+)) vs vs
<<{20,40,60,80},{10,20,30,40},{4,8,12,16}>,<{10,20,30,40},{6,12,18,24},{3,6,9,12}>,<{4,8,12,16},{3,6,9,12},{2,4,6,8}>>
>>> let vv = vector [vector [1,-1,1], vector [-1,1,-1], vector [1,-1,1]]
>>> mesh1 (\x -> comb21 (\y z-> x*(y+z))) vv vs vs
<<{16,32,48,64},{8,16,24,32},{-2,-4,-6,-8}>,<{8,16,24,32},{-6,-12,-18,-24},{-3,-6,-9,-12}>,<{-2,-4,-6,-8},{-3,-6,-9,-12},{2,4,6,8}>>

returns the number of elements in a value.

>>> length $ vector [1,2,3,4,5]
5

returns a vector with the indexes from another vector.

>>> index $ vector [1,1,1,1,1,1,1]
<1,2,3,4,5,6,7>

fanout repeats an element. As a process network it distributes the same value or signal to all the connected processes down the line. Depending on the target platform and the refinement decisions involved, it may be interpreted in the following implementations:

• global or shared memory in case of a massively parallel platform (e.g. GPU)
• a (static) memory or cache location in memory-driven architectures (e.g. CPU)
• a fanout in case of a HDL system
• a broadcast in case of a distributed system

fanoutn is the same as fanout, but the length of the result is also provided.

>>> fanoutn 5 1
<1,1,1,1,1>

generate creates a vector based on a kernel function. It is just a restricted version of recur.

>>> generate 5 (+1) 1
<6,5,4,3,2>

iterate is a version of generate which keeps the initial element as well. It is a restricted version of recuri.

>>> iterate 5 (+1) 1
<5,4,3,2,1>

Instance of first

>>> S.first $ vector [1,2,3,4,5]
1

Instance of last

>>> S.last $ vector [1,2,3,4,5]
5

creates a vector of all the initial segments in a vector.

>>> inits $ vector [1,2,3,4,5]
<<1>,<1,2>,<1,2,3>,<1,2,3,4>,<1,2,3,4,5>>

creates a vector of all the final segments in a vector.

>>> tails $ vector [1,2,3,4,5]
<<1,2,3,4,5>,<2,3,4,5>,<3,4,5>,<4,5>,<5>>

Returns the initial segment of a vector.

>>> init $ vector [1,2,3,4,5]
<1,2,3,4>

Returns the tail of a vector.

>>> tail $ vector [1,2,3,4,5]
<2,3,4,5>

concatenates a vector of vectors.

>>> concat $ vector [vector[1,2,3,4], vector[5,6,7]]
<1,2,3,4,5,6,7>

reverses the elements in a vector.

>>> reverse $ vector [1,2,3,4,5]
<5,4,3,2,1>

groups a vector into sub-vectors of n elements.

>>> group 3 $ vector [1,2,3,4,5,6,7,8]
<<1,2,3>,<4,5,6>,<7,8>>

right-shifts a vector with an element.

>>> vector [1,2,3,4] `shiftr` 8
<8,1,2,3>

left-shifts a vector with an element.

>>> vector [1,2,3,4] `shiftl` 8
<2,3,4,8>

rotates a vector to the right.

>>> rotr $ vector [1,2,3,4]
<4,1,2,3>

rotates a vector to the left.

>>> rotl $ vector [1,2,3,4]
<2,3,4,1>

rotates a vector to the left or to the right depending on the index:

• (> 0) : rotates the vector right with the corresponding number of positions.
• (= 0) : does not modify the vector.
• (< 0) : rotates the vector left with the corresponding number of positions.

takes the first n elements of a vector.

>>> take 5 $ vector [1,2,3,4,5,6,7,8,9]
<1,2,3,4,5>

drops the first n elements of a vector.

>>> drop 5 $ vector [1,2,3,4,5,6,7,8,9]
<6,7,8,9>

takes the first elements in a vector until the first element that does not fulfill a predicate.

>>> takeWhile (<5) $ vector [1,2,3,4,5,6,7,8,9]
<1,2,3,4>

returns a vector containing only the elements of another vector whose index satisfies a predicate.

>>> filterIdx (\x -> x `mod` 3 == 0) $ vector [0,1,2,3,4,5,6,7,8,9]
<2,5,8>

does a stride-selection on a vector.

>>> stride 1 3 $ vector [1,2,3,4,5,6,7,8,9]
<1,4,7>

returns the n-th element in a vector, or Nothing if n > l.

>>> get 3 $ vector [1,2,3,4,5]
Just 3

the same as get but with flipped arguments.

unsafe version of <@. Throws an exception if n > l.

selects the elements in a vector at the incexes contained by another vector.

The following versions of this skeleton are available, the number suggesting how many nested vectors it is operating upon: gather[1-5]

>>> let ix = vector [vector [1,3,4], vector [3,5,1], vector [5,8,9]]
>>> let v = vector [11,12,13,14,15]
>>> gather2 ix v
<<Just 11,Just 13,Just 14>,<Just 13,Just 15,Just 11>,<Just 15,Nothing,Nothing>>

the same as gather1 but with flipped arguments

The following versions of this skeleton are available, the number suggesting how many nested vectors it is operating upon.

(<@>), (<<@>>), (<<<@>>>), (<<<<@>>>>), (<<<<<@>>>>>),

replaces the n-th element in a vector with another.

>>> replace 5 15 $ vector [1,2,3,4,5,6,7,8,9]
<1,2,3,4,15,6,7,8,9>

scatters the elements in a vector based on the indexes contained by another vector.

>>> scatter (vector [2,4,5]) (vector [0,0,0,0,0,0,0,0]) (vector [1,1,1])
<0,1,0,1,1,0,0,0>

zipx is a template skeleton for "zipping" a vector of signals. It synchronizes all signals (of the same MoC) in a vector and outputs one signal with vectors of the synced values. For each signal in the input vector it requires a function which translates a partition of events (see ForSyDe.Atom.MoC) into sub-vectors.

There exist helper instances of the zipx skeleton interface for all supported MoCs.

unzipx is a template skeleton to unzip a signal carrying vectors into a vector of multiple signals. It required a function that splits a vector of values into a vector of event partitions belonging to output signals. Unlike zipx, it also requires the number of output signals. The reason for this is that it is impossible to determine the length of the output vector without "sniffing" the content of the input events, which is out of the scope of skeletons and may lead to unsafe behavior. The length of the output vector is needed in order to avoid infinite recurrence.

There exist helper instances of the unzipx skeleton interface for all supported MoCs.