Mapping a window function over a repa array with a boundary case

Question

Problem

I'm looking for a function in the repa library that may already exist. I'd like a function that:

1. Takes a 2D array
2. Two integers specifying a window size
3. In each window of the given size over the 2D array, calculate a new value e.g. the small value in this particular window.

Example

Mapping a min function with a 3x3 window over:

| 1 2 3 4 3
  4 5 6 7 2
  7 8 9 4 2
  5 4 8 1 6
  8 5 3 3 2 |

Would return:

| 1 1 2 2 2
  1 1 2 2 2
  4 4 1 1 1
  4 3 1 1 1
  4 3 1 1 1 |

Note that I'm using a scheme akin to the BoundClamp  constructor in Data.Array.Repa.Stencil. This isn't a stencil convolution, i.e. it is not applying a stencil to every element of a 2D array. Instead, it is performing a function at each window on the array, with out-of-range elements at the edges being assigned the closest value at the edge of the 2D array.

Type of possible solution

The function might look something like:

mapF
  :: Source r a
  => Boundary a            -- ^ How to handle the boundary of the array.
  -> (Int,Int)             -- ^ window size in the X and Y direction.
  -> (Array r DIM2 a -> b) -- ^ function over window e.g. to return the minimum value.
  -> Array r DIM2 a        -- ^ Array to apply function to.
  -> Array r DIM2 b

Is this something that either already exists, or would be trivial to code up?

Answer 1

I am rusty on my repa, but beleive you can use traverse and manually detect the array boundaries. Consider the type:

traverse ::
  (Source r a, Shape sh, Shape sh') =>
  Array r sh a
  -> (sh -> sh') -> ((sh -> a) -> sh' -> b) -> Array D sh' b

The function takes the original array, a function that produces the new shape, a function that takes a lookup-function and an index to produce a new value, and results in the new (delayed) array.

An easy solution is to check all neighbors of your index, controlling for the bound using min and max:

import qualified Data.Array.Repa as R
import           Data.Array.Repa (Z(..), traverse, fromListUnboxed, toList, (:.)(..))
import Prelude
import Data.List.Split

main = do let a = fromListUnboxed (Z :. h :. w) ( [1..6] ++ [2..7] ++ [3..8] ++ [4..9] ++ [5..10] ::  [Int])
              r = traverse a id (\f (Z :. y :. x) -> minimum [f (Z :. yi :. xi) | xi <- idx w x, yi <- idx h y])
          printArray a
          printArray r
  where
    idx b i = map (bound b) [i, i+1, i-1]
    bound b = min (b-1) . max 0
    w = 6 :: Int
    h = 5 :: Int

    printArray = putStrLn . unlines . map show . chunksOf w . toList

The main reason to object to this solution would be performance (many comparisons of the same numbers, many bounds checks that should be statically eliminated). OTOH, your question only asked for an easy solution and didn't seem overly concerned with performance.

I am also interested if there is a faster solution built-in to Repa.