输出L形矩阵时避免双重遍历

Question

我正在尝试遍历L Shape中的 Lists 列表。例如：lShapedTraverse [[1,2,3],[4,5,6],[7,8,9]]将导致[[1,2,3,6,9],[4,5,8],[7]]

我有以下算法可以给出所需的输出：

lShapedTraverse :: [[a]] -> [[a]]
lShapedTraverse [] = []
lShapedTraverse [xs] = [xs]
lShapedTraverse (xs:xss) = let (rest, col) = ((map init xss), (map last xss))
                           in (xs ++ col) : lShapedTraverse rest

这是遍历列表列表两次以获得init和，我认为可以使用可以在一次遍历中last完成的自定义函数来避免这种情况。initAndLast

我想看看我是否可以做一个更有效的实现和惯用的 Haskell。

Answer 1

我们可以编写initAndLast，但它对性能没有太大帮助，因为对于结果的每个元素仍然需要做很多工作。

我们确实希望在列表的开头工作，这样我们只需进行恒定的工作量即可获取元素。我们可以通过从左到右翻转矩阵来安排它map reverse。现在我们总是使用第一行和第一列。我们只需要记住在生产行部件时取消反转它们即可。

-- L shapes from top left to top right then down to bottom right
lShaped :: [[a]] -> [[a]]
lShaped = lShaped' . map reverse

-- L shapes from top right backwards to top left then down to bottom left
lShaped' :: [[a]] -> [[a]]
lShaped' [] = []
lShaped' ([]:_) = []
lShaped' (xs:xss) = (reverse xs ++ map head xss) : lShaped' (map tail xss)

我们需要两种基本情况来处理比高度高和比高度宽的矩形 - 您的代码缺少其中之一。

或者，我们可以尝试使用库函数而不是进行手动递归。

该函数沿着向上倾斜的线将矩形切成两部分。 n是上/左部分第一行的长度，或者如果 n 大于矩形的宽度，则必须将其想象为定义切割线右上角点的矩形外部的坐标，以便某些在我们开始剪切之前，完整的行将出现在上/左部分。

slice :: Int -> [[a]] -> ([[a]], [[a]])
slice n xss = unzip (zipWith splitAt [n,n-1 ..] xss)

使用切片可以很好地分割 L 的水平和垂直部分的元素，但垂直部分没有以有用的方式排列。我们可以在矩阵转置上再次使用切片来将它们放入正确的列表中，而不是尝试重新排列它们。最后我们将水平和垂直部分放在一起 zipWith (++)。

lShaped'' :: [[a]] -> [[a]]
lShaped'' [] = []
lShaped'' xss = zipWith (++) rowParts (reverse colParts)
  where
    (rowParts, _) = slice width xss
    (_, colParts) = slice width (transpose xss)
    width = length (head xss)

我不知道我是否比手动递归更喜欢这个解决方案，但确实如此。将长度和数字引入列表算法总是有点遗憾，但目前我没有看到更干净的方法。