输出L形矩阵避免二次遍历

Question

我正在尝试遍历 L Shape 中的列表列表。例如：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 翻转矩阵 left-to-right 来安排它。现在我们总是使用第一行和第一列。我们只需要请记住 un-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)

我们需要两个基本案例来处理比实际高度高的矩形比身高还宽——你的代码少了一个其中

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

此函数沿 upward-sloping 线将矩形切成两部分。 n 是 upper/left 部分第一行的长度，或者如果 n 更大比矩形的宽度你必须把它想象成一个坐标在定义切割的 top-right 点的矩形之外行，这样一些完整的行将出现在之前的 upper/left 部分我们切入正题。

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)

我不知道我是否比手动递归更喜欢这个解决方案但就是这样。引入长度总是有点丢脸和数字到列表算法中，但我看不到更简洁的方法时刻.

Answer 2

由于有多种表示输入矩阵的可能性，我们可以尝试将“导航”（即元素的选择）与实际矩阵表示分开。

为了实现这一点，我们可以轻松编写一个递归函数，生成要从输入矩阵中提取的二维笛卡尔坐标列表：


{-#  LANGUAGE  TupleSections        #-}

-- returns 2D list of Cartesian coordinates for entries of L-shaped matrix:
coordList :: Int -> [[(Int,Int)]]
coordList n = go n 0 n  where   -- rl: Row Length   sr: Starting Row
    go n sr rl = ((map (sr,) [0..(rl-1)]) ++ (map (,rl-1) [(sr+1)..(n-1)]) )  :
                  if (rl > 1)  then  go n (sr+1) (rl-1)  else  []

在 ghci 解释器下检查：

 λ> 
 λ> coordList 3
 [[(0,0),(0,1),(0,2),(1,2),(2,2)],[(1,0),(1,1),(2,1)],[(2,0)]]
 λ>

接下来，我们天真地使用低效的 !! 来测试我们的新 coordList 函数。列表提取运算符：

 λ> printAsLines xs = mapM_  (putStrLn . show)  xs
 λ> 
 λ> xss = [[1,2,3], [4,5,6], [7,8,9]]
 λ> 
 λ> printAsLines $ map (map (\(i,j) -> ((xss !! i) !! j))) $ (coordList 3)
 [1,2,3,6,9]
 [4,5,8]
 [7]
 λ>

这可能效率低下，但它是正确的。因此，我们可以通过用向量和列表替换列表来获得更高效的版本！运算符由等效向量 !运算符：

import qualified  Data.Vector as  V

-- vector-based version:
lShapedTraverse :: [[a]] -> [[a]]
lShapedTraverse xss = 
    let
         rank   = length (head xss)  -- matrix rank
         pairs  = coordList rank     -- 2D list of Cartesian coordinates
         matrix = V.fromList (map  V.fromList  xss)  -- 2D vector
    in
         map  (map (\(i,j) -> ((matrix V.! i) V.! j)))  $  pairs

测试程序：

printAsLines :: Show α => [α] -> IO ()
printAsLines xs = mapM_  (putStrLn . show)  xs


main :: IO ()
main = do
    let  xss   = [[1,2,3], [4,5,6], [7,8,9]]
         lMat1 = lShapedTraverse  xss

    putStrLn $ "res1 = "
    printAsLines lMat1

程序输出：

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

输出L形矩阵避免二次遍历

Avoiding double traversal in outputting a L-shaped matrix

haskell

matrix

nested-lists

测试程序：

程序输出：