Изменение массивов в Haskell и запоминание индексов

Мне нужно преобразовать подмассив и, возможно, потребуется выполнить преобразование в подмассиве подмассива и так далее.

Существуют ли интуитивно понятные способы сделать это в 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, которые продолжают процедуру на подматрице, если решение недоступно.

7
задан Undreren 21 March 2012 в 13:51
поделиться