瞭解Haskell中的矩陣轉置函數

Question

這個矩陣轉置函數可以工作，但我試圖瞭解它的一步一步執行，我不明白。

transpose:: [[a]]->[[a]] 
    transpose ([]:_) = [] 
    transpose x = (map head x) : transpose (map tail x) 

與

transpose [[1,2,3],[4,5,6],[7,8,9]] 

返回：

[[1,4,7],[2,5,8],[3,6,9]] 

我不明白如何連接運算符正與地圖。它在同一個函數調用中連接x的每個頭部？怎麼樣？

是這個

(map head x) 

創建每個列表的頭元素的列表？

Answer 1

讓我們看一下函數的功能爲您的輸入例：

transpose [[1,2,3],[4,5,6],[7,8,9]] 
<=> 
(map head [[1,2,3],[4,5,6],[7,8,9]]) : (transpose (map tail [[1,2,3],[4,5,6],[7,8,9]])) 
<=> 
[1,4,7] : (transpose [[2,3],[5,6],[8,9]]) 
<=> 
[1,4,7] : (map head [[2,3],[5,6],[8,9]]) : (transpose (map tail [[2,3],[5,6],[8,9]])) 
<=> 
[1,4,7] : [2,5,8] : (transpose [[3],[6],[9]]) 
<=> 
[1,4,7] : [2,5,8] : (map head [[3],[6],[9]]) : (transpose (map tail [[3],[6],[9]])) 
<=> 
[1,4,7] : [2,5,8] : [3, 6, 9] : (transpose [[], [], []]) 
<=> 
[1,4,7] : [2,5,8] : [3, 6, 9] : [] -- because transpose ([]:_) = [] 
<=> 
[[1,4,7],[2,5,8],[3,6,9]] 

注意，在我選擇了減少條款的順序是不一樣的評價順序哈斯克爾會使用，但不會改變結果。

編輯：在回答你的問題編輯：

是這個

(map head x) 

創建每個列表的頭元素的列表？

是的。

Answer 2

負責運營商:將類型爲a的對象附加到[a]類型的列表中。在

(map head x) : transpose (map tail x) 

的LHS是一個列表（a = [b]），而RHS是列表（[a] = [[b]]）的列表，所以這樣的結構是有效的。其結果是

[x,y,z,...] : [[a,b,...],[d,e,...],...] = [[x,y,z,...], [a,b,...],[d,e,...],...] 

---

在你的情況，map head x和map tail x分割矩陣

x = [[1,2,3],[4,5,6],[7,8,9]] 

到

map head x = [1,4,7] 
map tail x = [[2,3],[5,6],[8,9]] 

（是的，map head x是頭元素的列表的每個列表。）第二部分移置（詳細步驟見@sepp2k的答案），形成

transpose (map tail x) = [[2,5,8],[3,6,9]] 

所以利弊-ING [1,4,7]到這給

map head x : transpose (map tail x) = [1,4,7] : [[2,5,8],[3,6,9]] 
            = [[1,4,7] , [2,5,8],[3,6,9]] 

Answer 3

ghci是你的朋友：

*Main> :t map head 
map head :: [[a]] -> [a] 
*Main> :t map tail 
map tail :: [[a]] -> [[a]]

即使你不明白map（你想快速糾正一個問題！），這些表達式的類型說明了如何他們工作。第一個是列表中的單個列表，所以讓我們給它一個簡單的向量來看看會發生什麼。

你可能想要寫

*Main> map head [1,2,3] 

但未能類型檢查：

<interactive>:1:14: 
    No instance for (Num [a]) 
     arising from the literal `3' at :1:14 
    Possible fix: add an instance declaration for (Num [a]) 
    In the expression: 3 
    In the second argument of `map', namely `[1, 2, 3]' 
    In the expression: map head [1, 2, 3]

記住，參數的類型是一個列表的列表，所以

*Main> map head [[1,2,3]] 
[1] 

獲得一個位更復雜

*Main> map head [[1,2,3],[4,5,6]] 
[1,4] 

做相同，但與tail代替head給

*Main> map tail [[1,2,3],[4,5,6]] 
[[2,3],[5,6]] 

正如你所看到的，transpose定義重複割去第一「行」與map head x和調換的休息，這是map tail x。

Answer 4

順便說一下，此功能在輸入[[1,2,3], [], [1,2]]之類的輸入時不起作用。但是，Data.List的轉置功能將接受此輸入，並返回[[1,1], [2,2], [3]]。

當我們調用遞歸transpose的代碼時，我們需要擺脫[]。

Answer 5

這些東西是相同的：

map head xxs 
map (\xs -> head xs) xxs 

它的λ-表達，這意味着我返回XS的頭對於每個XS 實施例：

map head [[1,2,3],[4,5,6],[7,8,9]] 
-> map (\xs -> head xs) [[1,2,3],[4,5,6],[7,8,9]] 
-> [head [1,2,3], head [4,5,6], head [7,8,9]] 
-> [1,4,7] 

它的簡單