Modifying arrays in Haskell and remembering indices

Question

I need to make transformations to a subarray, and might need to make transformations on a subarray of the subarray, and so on.

Is there intuitive ways of doing this in Haskell, such as defining a subarray or something like that? I read the section on arrays in "a gentle introduction to haskell", and it doesn't address it, and I have a hard time finding a way to do it.

It's for an implementation of the Hungarian Algorithm as described here on wikipedia.

So so far I have done the following:

import Array

step1 :: (Ord a , Num a) => Array (Int,Int) a -> Array (Int,Int) a
step1 a      = a // [ ((i,j), f (i,j) ) | (i,j) <- range (bounds a) ] where
    f (i,j)  = a!(i,j) - minRow i
    minRow i = minimum [ a!(i,j) | j <- [1..(snd . snd . bounds) a] ]

step2 :: (Ord a , Num a) => Array (Int,Int) a -> Array (Int,Int) a
step2 a      = a // [ ((i,j), f (i,j) ) | (i,j) <- range (bounds a) ] where
    f (i,j)  = a!(i,j) - minCol j
    minCol j = minimum [ a!(i,j) | i <- [1..(fst . snd . bounds) a] ]

The problem is that I don't know how to implement step 3 and 4, which continues the procedure on a submatrix, in case a solution is not readily available.

Answer 1

I found a way to work around, allthough it's a bit of a hack. And it only works on 2D arrays, ie arrays of type Array (Int,Int) Int. Here's what I did:

import Data.Array
import Control.Applicative

updateSubArr :: [Int] -> [Int] -> (Array (Int,Int) Int -> Array (Int,Int) Int)
                      -> Array (Int,Int) Int -> Array (Int,Int) Int
updateSubArr rows cols f arr    = arr // (zip [(i,j) | i <- rows, j <- cols ]
                                [ fSubArr!i | i <- range $ bounds subArr ]) where
fSubArr = f subArr
subArr  = subArray cols rows arr

subArray rows cols arr  = subArr where
    js      = length cols
    is      = length rows
    subArr      = array subBounds $ zip (range subBounds)
                             [ arr!(i,j) | i <- rows, j <- cols ]
    subRange    = range subBounds
    subBounds   = ((1,1),(is,js))

Could this be made to work for a general Array a b?