Haskell repa - how to reduce array and return index?

Question

In GNU Octave, this code is

[e, ix] = min(X); 

returns the minimum element and its location. How do you do this in repa for an arbitrary binary function?

Here is what I came up with:

 min x = z $ foldl' f (e,0,0) es where (e:es) = toList x f (a,ix,r) b = let ix' = ix+1 in if a < b then (a,ix',r) else (b,ix',ix') z (a,ix,r) = (a,r) 

In the above example, we convert the repa 1D matrix to a list and use foldl '(from Data.List) with two accumulators - one to calculate iterations (ix) and the other to maintain the position of min element (r). But the whole point of using repa is to use arrays, not lists!

In repa, there are two folds for the Array type (foldS and foldP), but they can only accept functions of the type (a → a → a) - that is, I cannot pass a tuple with batteries to it. There is also a traverse, which can basically reduce a 1D array to a scalar array:

 min x = traverse x to0D min where to0D (Z:.i) = Z min f (Z) = ??? -- how to get elements for comparison? 

The first thing that comes to mind is

 [f (Z:.i) | i <- [1..n]], where n = (\(Z:.i) -> i) $ extent x 

But it also converts the array to a list, rather than doing the calculations in the array.

Answer 1

I am not an expert in Repa, but it seems to work with arrays with 1-D. Perhaps it can be adapted for other measurements.

 import Data.Array.Repa indexed arr = traverse arr id (\src idx@ (Z :. i) -> (src idx, i)) minimize arr = foldP fht where (Z :. n) = extent arr arr' = indexed arr h = arr' ! (Z :. 0) t = extract (Z :. 1) (Z :. (n-1)) arr' f min@ (valMin, iMin) x@ (val, i) | val < valMin = x | otherwise = min 

Answer 2

At the risk of revitalizing the zombie post, here is an arbitrary size decision I developed (which, considering the comments, is exactly what @hammar suggested). Due to the strange nature of foldAllP , which I use as an identity element when merging tuples, you also need to provide the upper bound of the minimum array you are looking for.

 import Data.Array.Repa import Data.Array.Repa.Eval import Data.Array.Repa.Repr.Unboxed minimize :: (Shape sh, Source ra, Elt a, Unbox a, Monad m, Ord a) => Array r sh a -> a -> m (a,sh) minimize arr upperBound = do -- Zip the array with its (Int representation of) indices let zippedWithIndex = Data.Array.Repa.traverse arr id (\f idx -> (f idx, toIndex (extent arr) idx)) -- Define a function that compares two tuple of (a,Int) on the value of the first entry let minimumIndex t@ (v,_) t'@(v',_) = if v < v' then t else t' -- Do a parallel fold of all elements in the array (min,idx) <- foldAllP minimumIndex (upperBound, error "Empty array") zippedWithIndex -- convert the indice back from its Int representation return (min, fromIndex (extent arr) idx) 

Naturally, if your array contains a type with an instance of Bounded , you can make a more convenient function

  minimize' arr = minimize arr maxBound 

Some tests you can run on the command line:

  λ> let x = fromListUnboxed (ix2 2 2) [20, 30, 10, 40] :: Array U DIM2 Int λ> minimize' x (10,(Z :. 1) :. 0)