在Haskell中修改数组并记住索引

Question

我需要对子数组进行转换,并且可能需要在子数组的子数组上进行转换,依此类推.

是否有直观的方法在Haskell中执行此操作,例如定义子数组或类似的东西？我在"对haskell的一个温和的介绍"中阅读了关于数组的部分,并没有解决它,我很难找到一种方法来实现它.

这对匈牙利算法的实现所描述这里的维基百科.

所以到目前为止我做了以下事情:

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] ]

问题是我不知道如何实现步骤3和4,如果解决方案不容易获得,则继续在子矩阵上执行该过程.

Answer 1

我找到了一种解决方法，尽管这有点麻烦。它只适用于二维数组，即 类型的数组Array (Int,Int) Int。这就是我所做的：

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))

这可以为将军服务吗Array a b？