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

Question

关闭。这个问题是opinion-based .它目前不接受答案。












想改进这个问题？更新问题，以便 editing this post 可以用事实和引用来回答它.


上个月关门。







Improve this question




我正在尝试遍历 L 形列表中的列表。例如: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

这是遍历列表列表 2 次以获得 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)

使用 slice 将元素很好地拆分为水平和
Ls 的垂直部分，但垂直部分没有排列成
有用的方法。与其尝试重新排列它们，我们可以再次使用 slice
在矩阵的转置上将它们放在正确的列表中。
最后我们把水平和垂直的部分放在一起 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)

我不知道我是否比手动递归更喜欢这个解决方案
但它就在那里。引入长度总是有点可惜
和数字进入列表算法，但我没有看到更清洁的方法
片刻。