-3

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]]
Fyodor Soikin
  • 78,590
  • 9
  • 125
  • 172
Gerardo Galan
  • 21
  • 2
  • 2
    I would do this by doing `map length` to get the length of all the sublists, `concat`-ing to flatten the nested list, shifting this whole flattened list, and then re-splitting the flattened shifted list using the lengths you got in the first step. – bradrn May 05 '20 at 04:42
  • 3
    Can you share what you've done so far? – lsmor May 05 '20 at 09:18

1 Answers1

1

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.

Redu
  • 25,060
  • 6
  • 56
  • 76
  • 1
    the assumption seems really arbitrary. a declarative approach could be to fill in any given (tree-like) structure from a linear supply of values, taken (with shifting) from that same structure's fringe (i.e. flattened list). (I [answered](https://stackoverflow.com/questions/50554603/fill-a-nested-structure-with-values-from-a-linear-supply-stream/50588667#50588667) something like this once or twice, with CPS code in Scheme/pseudo-Haskell). :) I think that approach could be applicable here as well. – Will Ness May 05 '20 at 11:23
  • @WillNess I based my assumption on the given test casess being sorted on length but yes, you may still call it arbitrary. Agree that flattening, rotating and reconstructing the nested structure by iterating over the original nested list is a good idea and would most possibly be much more efficient. – Redu May 05 '20 at 12:27