Correct way to group arrays of different sizes

Skip to first unread message

Даниил Дворянов

Apr 20, 2021, 1:04:27 PMApr 20
to Accelerate

I am trying to implement APL's key operator in Haskell using Accelerate.

My first attempt to type key operator looks like this:

key :: (Shape sh, Shape sh', Elt k, Elt v, Elt r)
    => (Acc (Array sh k) -> Acc (Array sh v) -> Acc (Array sh' r))
    -> Acc (Array (sh :. Int) k)
    -> Acc (Array (sh :. Int) v)
    -> Acc (Array (sh :. Int) k, Array (sh' :. Int) r)

The return type contains two arrays, that are supposed to have the same outer dimension. The first array contains unique keys, while the second array is supposed to contain a list of values corresponding to every key from the first array. However, since key operator assumes grouping the array of values by the respective keys, the number of values for each group will always be different. But since Accelerate allows only flat arrays, all of the groups have to be the same size.

I have been thinking of several possible workarounds for this, such as use the maximum length of a group for shape, and fill the unused space in other groups with default values (works in my case, might not work in general and might not be efficient); or add a new output vector which specifies the size of each group (in that case, the return type would be Acc (Vector Int, Array (sh :. Int) k, Array sh' r). 

Since I am new to array programming, it might be that I am missing something. Perhaps there is already an implementation of the key operator that I am not aware of? Or maybe there is a better way to represent "arrays of lists of arrays" in Accelerate?

Thank you in advance,
Danyil Dvorianov
Reply all
Reply to author
0 new messages