Essentially sequential array transformations in in Repa

Question

I wonder whether there is an analogue of (//) in repa?

It is needed for array transformations that cannot be parallelized. For example if the function requires the whole array to change a single entry of an array and than it is applied to a new array and so on (and it should be run sequentially).

Answer 1

(//) can be implemented in terms of Data.Array.Repa.fromFunction:

import Data.Array.Repa

(//) :: Shape sh => Array sh a -> [(sh,a)] -> Array sh a
(//) arr us = fromFunction (extent arr) (\sh -> case lookup sh us of
                                                 Just a  -> a
                                                 Nothing -> index arr sh)

fromFunction can be passed a function of type Shape sh => s -> a which itself can make use of the entire array.

The above implementation performs all the updates in one pass.

Answer 2

One potential problem with (//) is that it requires searching down the list to find the value for each element. If the array or the list are large, this can get expensive.

Another option is to leverage a handy function from Data.Vector:

modify :: Vector v a => (forall s. Mutable v s a -> ST s ()) -> v a -> v a

This has the possibility of doing the update in place if it is safe. So something like

import Data.Vector.Unboxed as V
import Data.Vector.Mutable.Unboxed as M
import Data.Array.Repa as R

(///) :: Shape sh => Array sh a -> [(sh,a)] -> Array sh a
(///) arr us = R.fromVector sh . modify f $ R.toVector arr
  where
  sh = extent arr
  f mv = forM_ us $ \(k,x) -> do
    M.write mv (R.toIndex sh k) x

On my laptop, I tested this for a 1-million-element DIM1 array, updating 100 entries, and got these times: (//): 3.598973 (///): 2.0859999999999997e-3