如何在Haskell中擴展矩陣

Question

我一直在試圖創建一個函數，它返回給定的矩陣並添加一行&列，其數字是行/列中數字的總和 數字sum列中的數字...

例如

(1 2 
3 4) 

到

(1 2 3 
3 4 7 
4 6 10) 

我首先想到的是像

> extend1 :: Int -> Array (Int,Int) Int 
> extend1 ((a,b),(c,d)) = n where 
>     n = array ((a,b),(c,d),(n,n)) 

，因爲我必須使用 「陣列」。現在我不知道如何繼續。這是好還是完全錯誤？

Answer 1

首先，您應該瞭解如何與haskell數組接口。在Data.Array中找到Array數據類型，因此有關完整的詳細信息，請查看該模塊的文檔。

請注意，我省略了所有這些功能中的Ix i約束條件。這種情況並不重要。

bounds :: Array i e -> (i, i)：該函數返回數組的最小和最大索引。對於一維數組，這些只是數字。對於二維數組，它是左上角和右下角（對於矩陣）。

array :: (i, i) -> [(i, e)] -> Array i e：該函數根據邊界的最小/最大值對以及關聯列表創建一個數組;即從索引到值的映射。您的初始示例可寫爲array ((0,0),(1,1)) [((0,0),1),((0,1),2),((1,0),3),((1,1),4)]

assocs :: Array i e -> [(i, e)]：這是array的'相反'。所以，arr == array (bounds arr) (assocs arr)。

現在的功能：

extendArray :: Num e => Array (Int, Int) e -> Array (Int, Int) e 
extendArray arr = 
    let 
     arr' = assocs arr 
     ((xMin, yMin), (xMax, yMax)) = bounds arr 
     newCol = [ ((n, yMax + 1) , sum [ v | ((x,_),v) <- arr', x == n]) | n <- [xMin .. xMax]] 
     newRow = [ ((xMax + 1, n) , sum [ v | ((_,y),v) <- arr', y == n]) | n <- [yMin .. yMax]] 
     newCorner = [((xMax + 1, yMax + 1), sum $ map snd arr')] 
     newArr = array ((xMin, yMin), (xMax + 1, yMax + 1)) (arr' ++ newCol ++ newRow ++ newCorner) 

    in newArr 

讓我們打破這裏發生了什麼。到目前爲止，let聲明中的前兩行應該是不言自明的。第三行，newCol，是魔術發生的地方。它使用列表解析，所以如果你不熟悉它們，請參閱here。

n <- [xMin .. xMax]：這部分獲得所有可能的x值。

[ v | ((x,_),v) <- arr', x == n]：對於列表arr'中的所有值，讀取的索引的x座標等於n，返回該座標處的值。

((n, yMax + 1) , sum ...創建一個新索引，其列爲1加上舊數組的最大值（因此舊矩陣的右邊爲1列），其行數爲n，其值爲前一行的總和（即 - 行n中所有值的總和）。

newRow以相同的方式工作，但行和列顛倒。

newCorner獲取矩陣中的所有值，計算它們的總和，並將此值放置在新數組的適當索引處。

newArr只是將所有步驟組合到一個新的數組中。顯然，每個方向的邊界都會增加一個。新數組的關聯將包括所有舊關聯以及我們計算出的新關聯。

所以：

>let x = array ((0,0),(1,1)) [((0,0),1),((0,1),2),((1,0),3),((1,1),4)] 
>x 
array ((0,0),(1,1)) [((0,0),1),((0,1),2),((1,0),3),((1,1),4)] 
>extendArray x 
array ((0,0),(2,2)) [((0,0),1),((0,1),2),((0,2),3),((1,0),3),((1,1),4),((1,2),7),((2,0),4),((2,1),6),((2,2),10)] 

注意，此實現效率不高（這不過是簡單）。在newRow中，我們遍歷整個矩陣xMax - xMin次（每個值爲n一次）。由於assocs總是以相同的順序返回元素（從左到右的行，從上到下的列），最好將列表arr'分爲長度爲yMax - yMin的列表;這會給我們一個行列表。但是我會把這個優化留給你。

Answer 2

使用你的元組的表示形式，並且沒有多少注意泛泛之處，下面是你的問題的一個解決方案。

type Square2 a = ((a,a), (a,a)) 
type Square3 a = ((a,a,a), (a,a,a), (a,a,a)) 

extend1 :: Num a => Square2 a -> Square3 a 
extend1 ((a,b), (c,d)) = 
    ((a, b, ab ) 
    , (c, d, cd ) 
    , (ac, bd, abcd)) 

    where 
    ab = a + b 
    cd = c + d 
    ac = a + c 
    bd = b + d 
    abcd = ab + cd 

注意我如何使用這兩種從輸入的模式和where條款中的定義撲殺變量定義。另請注意，在構建全新輸出的同時，我如何破壞和消耗輸入---一些元素被重用，但結構本身被破壞。最後，請注意我如何選擇元組內部的類型，使其能夠被Num類型類型常量和約束，從而允許我使用(+)進行添加。

類似的功能，通用和使用Array S有像

extend1A :: Num a => Array (Int,Int) a -> Array (Int, Int) a 

一個類型，我們已經失去了才知道的Array S的確切大小的能力，但它表明，我們的函數接受一個Array一些尺寸並返回另一個Array，其索引相同並且包含相同的Num受約束的類型。

array函數將第一個參數作爲一組邊界。我們需要根據輸入數組

extend1A ary0 = array bounds1 ... where 
    ((minX, minY), (maxX, maxY)) = bounds ary0 
    (maxX1, maxY1) = (succ maxX, succ maxY) 
    bounds1 = ((minX, minY, (maxX1, maxY1)) 

的bounds更新這些然後array以「ASSOCS」作爲第二個參數列表。我們可以將任何Array ix a視爲等同（大致）等同於聯繫人列表[(ix, a)]，其列出值爲「在索引ix處的值爲a」的值。要做到這一點，我們必須知道我們之前管理的ix類型的bounds。

要使用舊數據更新數組，我們可以修改舊數組的assocs以包含新信息。具體而言，這意味着extend1A看起來有點像

extend1A ary0 = array bounds1 (priorInformation ++ extraInformation) where 
    priorInformation = assocs ary0 
    extraInformation = ... 
    ((minX, minY), (maxX, maxY)) = bounds ary0 
    (maxX1, maxY1) = (succ maxX, succ maxY) 
    bounds1 = ((minX, minY, (maxX1, maxY1)) 

如果extraInformation是空的（[]）然後extend1A ary將等於ary上在其範圍的所有外部的輸入ary和undefined的範圍內的所有indicies。我們需要填寫extraInformation加總信息。

extend1A ary0 = array bounds1 (priorInformation ++ extraInformation) where 
    priorInformation = assocs ary0 
    extraInformation = xExtension ++ yExtension ++ totalExtension 
    xExtension = ... 
    yExtension = ... 
    totalExtension = ... 
    ((minX, minY), (maxX, maxY)) = bounds ary0 
    (maxX1, maxY1) = (succ maxX, succ maxY) 
    bounds1 = ((minX, minY, (maxX1, maxY1)) 

如果我們認爲延伸在三個陣列中，xExtension通過ab和extend1cd標記，所述yExtension通過extend1ac和bd標記和extend1標記由abcd那麼我們就可以計算各個所述totalExtension部分依次。

totalExtension是最容易的 - 它只是priorInformation中每個(i,a)對的「值分量」的總和。它也可能是xExtension或yExtension的「價值組成部分」的總和，但爲了儘可能顯得正確，我們將選擇第一個選項並將其安裝在右下角。

extend1A ary0 = array bounds1 (priorInformation ++ extraInformation) where 
    priorInformation = assocs ary0 
    extraInformation = xExtension ++ yExtension ++ totalExtension 
    sumValues asscs = sum (map snd asscs) 
    xExtension = ... 
    yExtension = ... 
    totalExtension = [((maxX1, maxY1), sumValues priorInformation)] 
    ((minX, minY), (maxX, maxY)) = bounds ary0 
    (maxX1, maxY1) = (succ maxX, succ maxY) 
    bounds1 = ((minX, minY), (maxX1, maxY1)) 

請注意，我們可以使用where子句來定義諸如sumValues將遍地出現新的功能。

然後我們可以通過priorInformation來計算擴展名作爲列表解析。我們需要在舊的關聯上收集一種特定的總和---總結一個索引固定的所有值。

xExtension = [((maxX1, yix) 
       , sumValues (filter (\((_, j), _) -> j == yix) priorInformation) 
      ) 
      | yix <- [minY .. maxY] 
      ] 

yExtension = [((xix, maxY1) 
       , sumValues (filter (\((i, _), _) -> i == xix) priorInformation) 
      ) 
      | xix <- [minX .. maxX] 
      ] 

然後我們就完成了。效率不高，但所有的部分一起工作。

extend1A ary0 = array bounds1 (priorInformation ++ extraInformation) where 
    priorInformation = assocs ary0 
    extraInformation = xExtension ++ yExtension ++ totalExtension 
    xExtension = [((maxX1, yix) 
       , sumValues (filter (\((_, j), _) -> j == yix) priorInformation) 
       ) 
       | yix <- [minY .. maxY] 
       ] 
    yExtension = [((xix, maxY1) 
       , sumValues (filter (\((i, _), _) -> i == xix) priorInformation) 
       ) 
       | xix <- [minX .. maxX] 
       ] 
    totalExtension = [((maxX1, maxY1), sum xExtension)] 
    ((minX, minY), (maxX, maxY)) = bounds ary0 
    (maxX1, maxY1) = (succ maxX, succ maxY) 
    bounds1 = ((minX, minY), (maxX1, maxY1)) 

Answer 3

使用HMATRIX：

import Numeric.LinearAlgebra 
import Numeric.LinearAlgebra.Util(col,row) 

m = (2><2) [1 , 2 
      ,3 , 4] :: Matrix Double 


extend m = fromBlocks [[m ,sr] 
         ,[sc, s]] 
    where 
    sr = col $ map sumElements (toRows m) 
    sc = row $ map sumElements (toColumns m) 
    s = scalar (sumElements sr) 


main = do 
    print m 
    print $ extend m 


(2><2) 
[ 1.0, 2.0 
, 3.0, 4.0 ] 
(3><3) 
[ 1.0, 2.0, 3.0 
, 3.0, 4.0, 7.0 
, 4.0, 6.0, 10.0 ]