控制陣列填寫哈斯克爾

比方說，我在有一個簡單的遞歸函數控制陣列填寫哈斯克爾

Z(i,j) = Sum(Z(i, k), k = 0..j-1) + Sum(Z(k, j), k = 0..i-1) 
Z(0,0) = 1

如果你在一個表中奠定了這一點，用（0,0）左下方和（i，j）的從右上角可以看到，一般來說，所有單元格只依賴於左側和下側的每個單元格，而左上角至右下角的對角線都可以並行計算。如果我想並行這個

// for Z[n][m] 
for(i = 0; i <= n; i++) { 
for(j = 0; j <= m; j++) { 
    for(k = 0; k < j; k++) { 
    Z[i,j] += Z(i, k) 
    } 
    for(k = 0; k < i; k++) { 
    Z[i,j] += Z(k, j) 
    } 
} 
}

，我可以簡單地收集：

對於像C語言，我可能實現動態編程填補左下角和工作我的方式列開始當前正在工作的對角線索引，然後在每個索引上分派適當的函數。

在Haskell，我可以這樣做：

z = array ((0,0), (10,10)) 
     [((i, j), 1 + (sum (map (\x -> z ! (i, x)) [0..j-1])) + 
       (sum (map (\x -> z ! (x, j)) [0..i-1]))) | i <- [0..10], j <- [0..10]]

有一對夫婦的事情，我不喜歡這個。 1：閱讀困難，不清楚發生了什麼。 2：我無法控制執行順序。我如何知道Haskell是否以最有效的方式填充陣列？有沒有一種方法可以在Haskell中實現，這樣既易於閱讀又可以控制計算流程？

來源

2017-01-01 Mike Flynn

從the docs：

array是在邊界爭論，並在關聯表的索引嚴格，但非嚴格的值。

所以，你的表達將計算只有你實際使用的條目。您的z實際上是您在問題頂部指定的遞歸函數的備忘錄表，並且運行時評估順序自然由代碼中的數據依賴關係控制。換句話說，由於懶惰，z ! (i, j)將被免費計算。

在你的代碼的可讀性的問題：我發現你的功能的實現遠比你的程序一個更具可讀性。 Haskell的代碼是接近了很多，你給使用數學稱爲編程語言規範：而關於增量索引和累積總數，在Haskell你實際上是在談論做遞歸調用z在一定範圍內的C代碼會談值並對結果進行求和。您可以使用列表解析而不是map使其看起來更類似於數學符號：

z = array ((0,0), (10,10)) 
     [((i, j), 1 + sum [z ! (i, k) | k <- [0..j-1]] 
        + sum [z ! (k, j) | k <- [0..i-1]]) | i <- [0..10], j <- [0..10]]

來源

2017-01-02 00:21:01

控制陣列填寫哈斯克爾

回答

相關問題