Haskell L-Shaped traversal of List of Lists-CodePudding

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 this following algorithm, that 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. Any inputs appreciated.

Thanks.

CodePudding user response：

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.

CodePudding user response：

If you are going to consume most of the output following implementation will work much faster.

lt :: [[a]] -> [[a]]
lt xs = zipWith3 go [0 ..] xs rotated
  where
    rotated = transpose $ fmap reverse xs
    l = length (head xs)
    go i as bs = take (l - i) as    drop (i   1) bs

Note that it won't behave exactly like your function

-- >>> lt [[]] --> []
-- >>> lt [[1, 2], [3, 4], [5, 6]] --> [[1,2,4,6],[3,5]]
-- >>> lt [[1], [3], [5]] -->[[1,3,5]]
 
-- >>> lShapedTraverse [[]]  --> [[]]
-- >>> lShapedTraverse [[1, 2], [3, 4], [5, 6]]  --> [[1,2,4,6],[3,5],[]]
-- >>> lShapedTraverse [[1], [3], [5]]  --> Exception: Prelude.last: empty list

Even better answer by @Daniel Wagner

lt = go . map reverse
  where
    go [] = []
    go ([] : _) = [] -- to support rectangular inputs like [[1], [3], [5]]
    go (xs : xss) = (reverse xs    map head xss) : go (map tail xss)