在Haskell中理解这个矩阵转置函数

ttcibm8c  于 2022-11-14  发布在  其他
关注(0)|答案(7)|浏览(115)

这个矩阵转置函数是有效的,但是我试图理解它的一步一步的执行,我不明白。

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

我不明白连接运算符是如何处理map的。它是在同一个函数调用中连接x的每个头?怎么做?
这是不是

(map head x)

创建每个列表的head元素的列表?

5kgi1eie

5kgi1eie1#

让我们看看函数对示例输入做了什么:

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)

创建每个列表的head元素的列表?
是的,是的。

ssgvzors

ssgvzors2#

cons运算符:将类型为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 xmap 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]]

(and是的,map head x是每个列表的头元素的列表。)第二部分被转置(有关详细步骤,请参见@sepp2k的答案)以形成

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

因此将[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]]
yqkkidmi

yqkkidmi3#

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

von4xj4u

von4xj4u4#

这些事情都是一样的:

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

它是lambda-expression,这意味着i返回每个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]

这很简单

xxb16uws

xxb16uws5#

顺便说一下,当给定一个像[[1,2,3], [], [1,2]]这样的输入时,这个函数不起作用。但是,来自Data.List的转置函数将接受这个输入,并返回[[1,1], [2,2], [3]]
当我们调用递归的transpose代码时,我们需要去掉[]

lo8azlld

lo8azlld6#

如果要使用headtail转置 * 矩形 * 数组,请事先确保列数相同,然后可以执行以下操作:

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)

显然,它也适用于方阵和单例,但当标准实现提供更多选项时,我看不出它有多大用处。

ovfsdjhp

ovfsdjhp7#

或者,您也可以定义自己的函数。我发现了一种在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)

相关问题