Avoiding double traversal in outputting a L-shaped matrix [closed]

Question

I am trying to traverse a list of Lists in L Shape. For example: lShapedTraverse [[1,2,3],[4,5,6],[7,8,9]] will result in [[1,2,3,6,9],[4,5,8],[7]]

I have the following algorithm which gives the desired output:

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

This is traversing the list of list 2 times to get init and last, which I think can be avoided using a custom function that can do initAndLast in one traversal.

I am trying to see if I can do a more efficient implementation and idiomatic Haskell.

Answer 1

We could write initAndLast, but it wouldn't help performance very much because that would still be a lot of work to do for each element of the result.

We really want to be working at the beginning of the lists so we can get at the elements with only a constant amount of work. We can arrange this by flipping the matrix left-to-right with map reverse. Now we always work with the first row and column. We just have to remember to un-reverse the row parts as we produce them.

-- 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)

We need the two base cases to deal with rectangles taller than they are wide as well as wider than they are tall - your code is missing one of these.

Alternatively we could try to use library functions rather than doing manual recursion.

This function slices a rectangle into two parts along an upward-sloping line. n is the length of the first row of the upper/left part, or if n is greater than the width of the rectangle you have to imagine it as a coordinate outside the rectangle defining the top-right point of the cutting line, so that some full rows will appear in the upper/left part before we get down to the cut.

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

Using slice splits up the elements nicely for the horizontal and vertical parts of the Ls, but the vertical parts aren't arranged in a useful way. Rather than try to rearrange them we can use slice again on the transpose of the matrix to get them in the right lists. Finally we put the horizontal and vertical parts together with 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)

I don't know if I like this solution better than the manual recursion but there it is. It's always a bit of a shame to introduce lengths and numbers into a list algorithm but I don't see a cleaner way at the moment.

Answer 2

As there are several possibilities to represent the input matrix, we can try to separate the “navigation”, i.e. choice of elements, from the actual matrix representation.

In order to achieve this, we can easily write a recursive function that produces the 2D list of Cartesian coordinates to be extracted from the input matrix:

{-#  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  []

Checking under the ghci interpreter:

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

Next, we test our new coordList function by naïvely using the inefficient !! list extraction operator:

 ?> 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]
 ?> 

This might be inefficient, but it is correct. And so we can have a more efficient version of this by replacing lists by vectors and the list !! operator by the equivalent vector ! operator:

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

Test program:

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

Program output:

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