仅使用 `!!` 和 `length` 实现矩阵的转置

Question

我正在考虑如何仅使用 !! 和 length 对 Haskell 中的矩阵进行转置。我已经编写了一个函数来获取矩阵在任何给定索引处的列 i:

getCol :: [[Int]] -> Int -> [Int] 
getCol [] i = []
getCol (xs:xss) i = if isMatrix xss then (xs !! i) : getCol xss i else []

另外，return 一行长度的函数：

rowLength :: [[Int]] -> Int
rowLength (x:xs) = length x

我现在的计划是用 getCol 的条目填充列表 n 次，其中 n 是我调用函数的列表的 rowLength .

因此，对于此示例列表：

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

-- rowLength ---> 3
-- then fill another list with every column of list, 
--     for the indices 0..n (with n being rowLength)
-- resulting in [[1,4,7],[2,5,8],[3,6,9]

问题是，我通常会使用 head 和 tail 函数来执行此操作，但我只能使用 length 和 !!.

目前我的想法是

trav :: [[Int]] -> [[Int]]
trav xxs n = if (n <= rowLength) then getCol xxs n+1 : getCol xxs n else ?

我唯一的问题是 else 案例。我知道它在 Haskell 中是强制性的，但我也知道我的实现对于 else 情况没有意义。这是我第一次使用函数式语言而不是像 Java 这样的命令式语言，所以我试图在这里为索引模拟一个循环，但不知道该怎么做:(

有人可以给我提示吗？非常感谢！！

Answer 1

您不需要 (!!) 或 length；您所需要的只是递归、(:) 和模式匹配。

transpose :: [[Int]] -> [[Int]]
transpose [] = []
transpose ([]:xss) = []
transpose m = let (h, t) = ht m in h : transpose t
  where
    ht :: [[Int]] -> ([Int], [[Int]])
    ht [] = ([], [])
    ht ((x:xs):xss) = let (hs, ts) = ht xss in (x:hs, xs:ts)

Try it online!

ht 是一个辅助函数，它为 [Int] 的列表提供 (heads, tails)。这就像做 (map head xss, map tail xss)。第二个等式采用具有结构 firstList:rest 的 [[Int]]，找到剩余列表 rest 的头部和尾部 (hs, ts)，然后附加 [=22= 的头部和尾部] 到 hs 和 ts。基本情况是一个空矩阵，其中没有更多列表可以找到其头部和尾部。

头部（元组的第一个元素）是矩阵的第一列（就像 map (!!0)）。因此，我们有转置矩阵的第一行 h，我们将其添加到转置其余列（t，尾部）的结果之前。基本情况是所有内部列表都是空的 ([]:xss)，所以我们 return []，空矩阵。所有其他列表都假定为空 - 没有验证输入确实是矩阵。行中的额外元素将为 silently ignored。 transpose [] 的情况仅用于转置空矩阵。

由于(!!)和length对于链表来说不是特别高效（前者是O(m)找到索引k处的元素，后者是O(n)），我建议避免使用它们。

但是，如果您真的想尝试索引，请先考虑如何生成索引。您需要两个列表，一个用于行号，一个用于列号。一旦有了这些，就需要交换它们（如果 i 是行号而 j 是列号，则 m!!i!!j 变为 m!!j!!i）。为此，您可以尝试递归、列表理解或两者。

Answer 2

回答我自己的问题也是因为解决方案实际上比我想象的要简单得多，使用我自己已经实现的功能。

trav :: [[Int]] -> [[Int]]
trav xss = transpose xss 0 

transpose :: [[Int]] -> Int -> [[Int]]
transpose xss n = if n < (rowLength xss) then getCol xss n : transpose xss (n+1)  else []

我什至没有意识到我不需要模拟循环。我原以为在 transpose 函数中，如果它最终分解为 else-case，它只会 return 自己的空列表。我几乎不知道这只是将它放入已经由递归建立的列表中！

Try it out :)

Answer 3

这不是你问的，也不是你目前感兴趣的水平，但出于好奇，这也可以定义为单行，

transp :: Traversable t => t [a] -> [[a]]
--   or,                   [[a]] -> [[a]]
transp  =  takeWhile (not . null) . unfoldr (Just . traverse (splitAt 1))

仅使用 `!!` 和 `length` 实现矩阵的转置

Implementing the transpose of a matrix using only `!!` and `length`

haskell

transpose

functional-programming

list