Search code examples
listhaskellrecursionfunctional-programmingnested-lists

Haskell rotate list of lists


I'm trying to implement the following function in Haskell, its a recursive traversal that receives an Int and a list of lists [[Int]] and shifts the elements of the inner lists to the right without altering the size of the lists. I was able to get a list with the numbers in the right order but I couldn't insert them back into their proper sublists.

shift_right::Int->[[Int]]->[[Int]]

example #1:

shift_right 1 [[1,2,3],[4,5,6]] => [[6,1,2],[3,4,5]]

example #2:

shift_right 3 [[],[1],[2,3],[4,5,6]] => [[],[4],[5,6],[1,2,3]]

Solution

  • Assuming that the empty lists only appear at the beginning and never in the middle then one approach could be, first to find a way to make a single rotation and then to repeat the same action n times for n rotations. I think we can use mapAccumL for this purpose.

    m = [[],[1],[2,3],[4,5,6]]
    s l = es ++ (rem ++ ls) : lss
          where
          (rem, (ls:lss)) = mapAccumL shifter [] fs
          shifter a bs    = ([last bs], a ++ (init bs))
          (es,fs)         = span (== []) l              -- split empties and fulls
    
    λ> s m
    [[],[6],[1,2],[3,4,5]]
    
    λ> s [[],[6],[1,2],[3,4,5]] -- carry from previous answer
    [[],[5],[6,1],[2,3,4]]
    
    λ> s [[],[5],[6,1],[2,3,4]] -- carry from previous answer
    [[],[4],[5,6],[1,2,3]]
    

    So now... since you show no attempt at all, it is your duty to come up with a code that invokes this function (or a part of this function) n times for n rotations Hint: preferablly without concatenating the empties.