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

Question

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

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

另外，还有一个返回行长度的函数：

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

我现在的计划是n用 的条目填充列表时间getCol，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]

问题是，我通常会使用headandtail函数来做到这一点，但我只能使用lengthand !!。

到目前为止我的想法是

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)

在线试试吧！

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

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

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

但是，如果您真的想尝试建立索引，请先考虑如何生成索引。您需要两个列表，一个用于行号，一个用于列号。一旦你有了这些，你需要交换它们（m!!i!!j变成m!!j!!iifi是一个行号并且j是一个列号）。为此，您可以尝试递归、列表推导式或两者兼而有之。