理解 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]]

我不理解如何使用concatenation operator和map函数。它是在同一个函数调用中将每个x的头连接起来吗？怎么做到的？

这是什么？

(map head x)

创建一个包含每个列表头元素的列表？

- andandandand

---

这不是一个答案，但通常当我尝试理解Haskell中的某些东西时，我会花一些时间在GHCi中试验。尝试在几个列表中使用“map head”或“map tail”，你将亲眼看到它们如何工作。如果你来自一个命令式的世界，映射和折叠可能有点难以理解。它们是你的主要循环结构 - 基本上替换了“for”和“while” - 所以你很快就会学会喜欢它们。 - rtperson

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]]

请注意，我选择缩减项的顺序与Haskell将使用的评估顺序不同，但这并不会改变结果。

编辑：针对您编辑后的问题：

是这样

(map head x)

创建由每个列表的头元素组成的列表吗？

是的，可以。

- sepp2k

---

你当时在使用调试器吗？ - andandandand

也许他自己写的？这并不太难写。 - ZyX

() 不会创建列表。而 () 内部的 map 和 transpose 则会创建列表。 - ZyX

@dmindreader：() 是 Unit，它在代码中不会出现。[] 是空列表。 - sepp2k

Answer 2

cons运算符:将一个类型为a的对象附加到类型为[a]的列表中。

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

左侧是一个列表（a = [b]），而右侧是一个列表的列表（[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]]

将[1,4,7]传递给cons函数，结果为

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]]

- kennytm

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）进行转置。

- Greg Bacon

Answer 4

以下内容是相同的：

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

这是一个lambda表达式，意思是对于每个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]

这很简单

- Beraliv

Answer 5

如果您想使用head和tail来转置矩形数组，并确保列数相同，则可以执行以下操作：

rectangularTranspose :: [[a]] -> [[a]]
rectangularTranspose m = rectTrans m []
  where
    rectTrans [] a = a
    rectTrans ([]:xss) a = rectTrans xss a
    rectTrans ((x:xs):xss) a = rectTrans a ((x:map head xss): rectTrans (xs:map tail xss) a)

---

它也适用于方形数组和单例，但显然当标准实现提供更多选项时，我不认为这有太多用处。

- Marco_O

Answer 6

或者，你可以自己定义一个函数。我发现在 Haskell 中只使用列表推导式实现矩阵转置的方法更简单。它适用于具有非空元素的通用 m* n 矩阵。

transpose' :: [[a]] -> [[a]]
transpose' xss = chop nrows [xs !! (j-1) | i <- [1..ncols], j <- take nrows [i, i+ncols ..]] 
                where nrows = length  xss
                      ncols = length(head xss) 
                      xs = concat xss 

chop :: Int -> [a] -> [[a]]
chop _ [] = []
chop n xs = take n xs : chop n (drop n xs) 

- Srinath

---

这并没有回答问题。一旦您拥有足够的声望，您将能够评论任何帖子；相反，提供不需要询问者澄清的答案。- 来自审核 - Benoît Fraikin

Answer 7

顺便说一下，当给定像[[1,2,3], [], [1,2]]这样的输入时，这个函数不起作用。然而，来自Data.List的转置函数将接受此输入，并返回[[1,1], [2,2], [3]]。

在调用递归的transpose代码时，我们需要摆脱[]。

- zhenjie

---

最好将此放入实际答案的注释中；发帖者不仅仅是想调用transpose，而是想弄清楚为什么它有效。 - MattoxBeckman