Control.Parallel.ScanVectorMachine.SegmentedScanVectorMachine

An instance of SegmentedScanVectorMachine provides a scalar type s, a vector type v, and a segmented vector (vector-of-vectors) type v' such that v implements the SVM operations over s and v' implements the SVM operations over v s.

This file contains a default instance for ScanVectorMachine V' (V S), given an instance ScanVectorMachine V S. In other words, given an implementation of vectors-of-scalars, this will produce an implementation of vectors-of-vectors-of-scalars.

This new type V' provides SVM operations over vectors-of-vectors-of-scalars; from the perspective of V', the vectors-of-scalars are called segments. Notice that V' uses vectors-of-scalars wherever ordinary scalars were previously used. For example, when the length operation is applied to a vector-of-vectors the result is not a scalar, but rather a vector-of-scalars giving the lengths of each of the segments. This phenomenon is crucial to the replication theorem and flattening transformation.

It turns out that V' is basically (,) -- but this is not exposed to the user. Blelloch outlines three encodings (figure 4.2): head-flags, length, and head-pointer. The implementation below uses the length style since it can represent zero-length vectors efficiently.

It is sometimes advantageous for hardware/platform providers to implement vectors-of-vectors-of-scalars directly (see NestedVectors.hs for the reasoning). To do this, implement the class SegmentedScanVectorMachine below.

Documentation

class (ScanVectorMachine v s, ScanVectorMachine v' (v' (v s))) => SegmentedScanVectorMachine v' v s