在函数范例中使用嵌套循环的迭代过程

Question

我正在通过重写一些旧的C++代码来学习函数式编程(在Haskell中).我正在研究的一个例子涉及Floyd-Warshall图搜索,它在2D NxN邻接矩阵上运行,以找到所有对之间的最短路径.它使用三个嵌套for循环来扫描2D阵列并迭代地达到解决方案.

C++代码通常是:

int size = adjacencyMatrix.size();
for ( int k = 0; k < size; k++)
{
    for ( int i = 0; i < size; i++)
    {
        for ( int j = 0; j < size; j++)
        {
            double sum = adjacencyMatrix[i][k] + adjacencyMatrix[k][j];
            if ( sum < adjacencyMatrix[i][j] )
            {
                    adjacencyMatrix[i][j] = sum;
            }
        }
    }
}

这种图搜索的关键是它的迭代方法.例如,上面的代码非常顺序; 它只能在适度的程度上进行并行化,因为在其他人完成之前不能进行某些计算.

此外,访问矩阵的索引意味着可以完成阵列中的一些巧妙操作.上图搜索的最里面的循环使用adjacencyMatrix[i][k],adjacencyMatrix[k][j]和adjacencyMatrix[i][j].我知道mapHaskell 中的函数,但这似乎没有使用数组索引那样的功能和灵活性.

除了试图模拟Haskell中的命令式过程之外,我无法弄清楚如何以"纯粹的"功能样式重写上述代码.

如何使用复杂的嵌套循环来访问数组索引(例如上面的图搜索)的迭代过程如何转换为功能范例？

Answer 1

除了试图模拟Haskell中的命令式过程之外,我无法弄清楚如何以"纯粹的"功能样式重写上述代码.

我不知道,你可以随时改写根本势在必行算法以多功能风格.也就是说,这就是人们如何在Haskell中翻译你的例子.请注意,通常情况下,每当您发现自己确实需要一些可变变量时,您可能希望使用STmonad.对于数组,您可以获得高效的array包.

这是该算法的完整翻译的样子

import Data.Array.Unboxed (UArray)
import Data.Array.ST (runSTUArray, newListArray, readArray, writeArray)
import Data.Maybe (fromMaybe)
import Control.Monad (when)
import Data.Foldable (for_)

-- | Takes as input the number of vertices, function to weigh edges, and returns
-- a matrix of the shortest distance between every two vertices.
floydWarshall :: Int -> ((Int,Int) -> Maybe Double) -> UArray (Int,Int) Double
floydWarshall n weight = runSTUArray $ do
    -- initialize the array with the right values
    arr <- newListArray ((0,0),(n-1,n-1))
                        [ if i == j then 0 else fromMaybe (1 / 0) (weight (i,j))
                        | i<-[0..(n-1)], j<-[0..(n-1)] ]

    -- iteratively improve the shortest distances
    for_ [0..(n-1)] $ \k ->
      for_ [0..(n-1)] $ \i ->
        for_ [0..(n-1)] $ \j -> do
          arr_ik <- readArray arr (i,k)
          arr_kj <- readArray arr (k,j)
          arr_ij <- readArray arr (i,j)
          let sum = arr_ik + arr_kj
          when (sum < arr_ij)
            (writeArray arr (i,j) sum)

    return arr