| 161 | === Shape Polymorphic Computations on Arrays === |
| 162 | |
| 163 | |
| 164 | The library provides a range of operation where the dimensionality of |
| 165 | the result depends on the dimensionality of the argument in a |
| 166 | non-trivial manner, which we want to be reflected in the type system. |
| 167 | Examples of such functions are generalised selection, which allows for |
| 168 | extraction of subarrays of arbitrary dimension, and generalised replicate, |
| 169 | which allows replication of an array in any dimension (or dimensions). For example, |
| 170 | given a three dimensional matrix, we can use select to extract scalar element values, |
| 171 | rows, columns, as well as two dimensional matrices along any of the three axes. |
| 172 | |
| 173 | For selection, we can informally state the relationship between dimensionality of |
| 174 | the argument, the selector, and the result as follows: |
| 175 | {{{ |
| 176 | select:: Array dim e -> <select dim' of dim array> -> Array dim' e |
| 177 | }}} |
| 178 | |
| 179 | Another example for such a generalised function would be a generalised |
| 180 | `map`, which can apply a function to all elements, all rows, all |
| 181 | columns, or submatrices of different orientation of a multidimensional |
| 182 | array. |
| 183 | |
| 184 | For the former example, we need a way to express the relationship between the |
| 185 | shape of the argument and the shape and orientation of the result, as well as |
| 186 | the numerical position of the structure (i.e., first, second, third element). |
| 187 | In case of the generalised `map`, we don't need the numerical information, since |
| 188 | the operation will be applied to all elements, rows, columns etc. |
| 189 | |
| 190 | To express this dependency between input and output shape and orientation, |
| 191 | as well as possibly a concrete position, the library provides the `Index` GADT, |
| 192 | which expresses a relationship between the source and the projected dimension. |
| 193 | It is defined as follows: |
| 194 | {{{ |
| 195 | data Index a initialDim projectedDim where |
| 196 | IndexNil :: Index a initialDim initialDim |
| 197 | IndexAll :: (Shape init, Shape proj) => |
| 198 | Index a init proj -> Index a (init :*: Int) (proj :*: Int) |
| 199 | IndexFixed :: (Shape init, Shape proj) => a -> |
| 200 | Index a init proj -> Index a (init :*: Int) proj |
| 201 | }}} |
| 202 | To refer to a specific element, the type parameter `a` is instantiated with the type `Int`, otherwise |
| 203 | with the unit type: |
| 204 | {{{ |
| 205 | type SelectIndex = Index Int |
| 206 | type MapIndex = Index () |
| 207 | }}} |
| 208 | Given this definition, the type of `select` now becomes |
| 209 | {{{ |
| 210 | select:: (U.Elt e, Shape dim, Shape dim') => Array dim e -> SelectIndex dim dim' -> Array dim' e |
| 211 | }}} |
| 212 | Example: |
| 213 | {{{ |
| 214 | arr:: Array (() :*: Int :*: Int :*: Int) Double |
| 215 | |
| 216 | arr' :: () :*: Int :*: Int |
| 217 | arr' = select arr (IndexFixed 3 (IndexAll (IndexAll IndexNil))) |
| 218 | }}} |
| 219 | We could generalise this further, to extract from any array `arr` which is at least one dimensional |
| 220 | the third element: |
| 221 | {{{ |
| 222 | arr:: Shape dim => Array (dim :*: Int) Double |
| 223 | |
| 224 | arr' :: Array dim Double |
| 225 | arr' = select arr (IndexFixed 3 IndexNil) |
| 226 | }}} |
| 227 | |
| 228 | |
| 229 | The index type is also used to express the type of generalised replicate |
| 230 | {{{ |
| 231 | replicate:: Array dim' e -> SelectIndex dim dim' -> Array dim e |
| 232 | }}} |
| 233 | which, given an array, can be used to expand it along any dimension. For example, |
| 234 | {{{ |
| 235 | simpleReplicate:: (U.Elt e, Shape dim) => Array dim e -> Int -> Array (dim :*: Int) e |
| 236 | simpleReplicate arr n = |
| 237 | replicate arr (IndexFixed n IndexNil) |
| 238 | }}} |
| 239 | replicates the argument array (which can of any dimensionality) `n` times and behaves |
| 240 | thus similarly to list replicate, whereas |
| 241 | {{{ |
| 242 | elementwiseReplicate:: (U.Elt e, Shape dim) => |
| 243 | Array (dim :*: Int) e -> Int -> Array (dim :*: Int :*: Int) e |
| 244 | elementwiseReplicate arr n = |
| 245 | replicate arr (IndexAll (IndexFixed n IndexNil)) |
| 246 | }}} |
| 247 | replicates each element of an array `n` times (similarly to `map (replicate n)` on lists). |
| 248 | |
| 249 | |
| 250 | Even though the index type serves well to express the relationship |
| 251 | between the selector/multiplicator and the dimensionality of the |
| 252 | argument and the result array, it is inconvenient to use, as the |
| 253 | examples demonstrate. We therefore do need to add another layer to |
| 254 | improve the usability of the library. |
| 255 | |
| 256 | Note that the library provides no way to statically check the pre- and |
| 257 | postconditions on the actual size of arguments and results. This has |
| 258 | to be done at run time using assertions. |
| 259 | |
186 | | === Shape Polymorphic Computations on Arrays === |
187 | | |
188 | | The array operations described in this and the following subsection |
189 | | are available on both strict and delayed arrays, and yield the same |
190 | | result, with the exception that in case of delayed arrays, the result |
191 | | is only calculated once its forced by calling `fromDArray` or `forceDArray`. No |
192 | | intermediate array structures are ever created. |
193 | | |
194 | | The library provides a range of operation where the dimensionality of |
195 | | the result depends on the dimensionality of the argument in a |
196 | | non-trivial manner, which we want to be reflected in the type system. |
197 | | Examples of such functions are generalised selection, which allows for |
198 | | extraction of subarrays of arbitrary dimension, and generalised replicate, |
199 | | which allows replication of an array in any dimension (or dimensions). |
200 | | |
201 | | For selection, we can informally state the relationship between dimensionality of |
202 | | the argument, the selector, and the result as follows: |
203 | | {{{ |
204 | | select:: Array dim e -> <select dim' of dim array> -> Array dim' e |
205 | | }}} |
206 | | |
207 | | To express this relationship, the library provides the index GADT, |
208 | | which expresses a relationship between the inital and the projected |
209 | | dimensionality. It is defined as follows: |
210 | | |
211 | | {{{ |
212 | | data Index a initialDim projectedDim where |
213 | | IndexNil :: Index a () () |
214 | | IndexAll :: (Shape init, Shape proj) => |
215 | | Index a init proj -> Index a (init :*: Int) (proj :*: Int) |
216 | | IndexFixed :: (Shape init, Shape proj) => a -> |
217 | | Index a init proj -> Index a (init :*: Int) proj |
218 | | |
219 | | type SelectIndex = Index Int |
220 | | type MapIndex = Index () |
221 | | }}} |
222 | | Given this definition, the type of `select` now becomes |
223 | | {{{ |
224 | | select:: (U.Elt e, Shape dim, Shape dim') => Array dim e -> SelectIndex dim dim' -> Array dim' e |
225 | | }}} |
226 | | Example: |
227 | | {{{ |
228 | | arr:: Array DIM3 Double |
229 | | select arr (IndexFixed 3 (IndexAll (IndexAll IndexNil))) |
230 | | }}} |
231 | | The index type is also used to express the type of generalised replicate: |
232 | | {{{ |
233 | | replicate:: Array dim' e -> SelectIndex dim dim' -> Array dim e |
234 | | }}} |
235 | | Even though the index type serves well to express the relationship |
236 | | between the selector/multiplicator and the dimensionality of the |
237 | | argument and the result array, it is somehow inconvenient to use, as |
238 | | the examples demonstrate. This is therefore another example where we |
239 | | need to add another layer to improve the usability of the library. |
240 | | |
241 | | Note that the library provides no way to statically check the pre- and |
242 | | postconditions on the actual size of arguments and results. This has |
243 | | to be done at run time using assertions. |
244 | | |
245 | | == Array Operations == |
246 | | |
247 | | Backpermute and default backpermute are two general operations which allow |
248 | | the programmer to express all structural operations which reorder or extract |
249 | | elements based on their position in the argument array: |
250 | | {{{ |
251 | | backpermute:: (U.Elt e, Shape dim, Shape dim') => |
252 | | Array dim e -> dim' -> (dim' -> dim) -> Array dim' e |
253 | | |
254 | | backpermuteDft::(U.Elt e, Shape dim, Shape dim') => |
255 | | Array dim e -> e -> dim' -> (dim' -> Maybe dim) -> Array dim' e |
256 | | }}} |
257 | | |
258 | | |
259 | | |
260 | | The following operations could be (and in the sequential implementation indeed are) expressed |
261 | | in terms of backpermute and default backpermute. However, a programmer should aim at using more |
262 | | specialised functions when provided, as they carry more information about the pattern of reordering. |
263 | | In particular in the parallel case, this could be used to provide significantly more efficient |
264 | | implementation which make use of locality and communication patterns. |
265 | | {{{ |
266 | | shift:: (Shape dim, U.Elt e) => Array dim e -> e -> dim -> Array dim e |
267 | | |
268 | | rotate:: (Shape dim, U.Elt e) => Array dim e -> e -> dim -> Array dim e |
269 | | |
270 | | tile:: (Shape dim, U.Elt e) => Array dim e -> dim -> dim -> Array dim e |
271 | | }}} |