Generating a list which is made by right shifting elements n times

Question

I am trying a problem recently. And in this case I am having few problems.

Input: generatingListforRightShifting 2 [1,2,3,4,5,6,7,8]
Output: [[1,2,3,4,5,6,7,8],[8,1,2,3,4,5,6,7],[7,8,1,2,3,4,5,6]]

As you understand this program will shift an element in right direction. The 1st argument indicates how many times it will do shifting. As a newbie I am trying solving it few well known list functions. and using recursion. But to me recursion idea is not clear. My code is:

generatingListforRightShifting' _ []=[]
generatingListforRightShifting' 0 x=x
generatingListforRightShifting' n xs=   newList where
                        newList=takeWhile(\i->[1..n] 
                                            <=n)(reverse(take 
                                           i(reverse xs))++reverse(drop i(reverse xs)))

I understand that the main mistake I'm doing is in the part takeWhile. But how can I iterate through n times. I have already made a program which directly shows the shifted result such as Input:generatingListforRightShifting 2 [1,2,3,4,5,6,7,8] Output: [7,8,1,2,3,4,5,6] But when I try to get all previous shifting I cannot.

Can anyone help me out here. I also welcome you if you give me the solving idea.

Answer 1

This is more commonly known as rotating instead of shifting. Rotating the list right once is simple, as there are methods to get the last element and the the sublist of all elements but the last.

rotateOnce lst = (last lst):(init lst)

Also note that the rotating twice is equivalent to calling rotateOnce twice. Therefore, the method could be implemented simply as a recursion from the previous result:

rotateN 0 lst = [lst]
rotateN n lst = lst : rotateN (n-1) ((last lst):(init lst))

(Note: that may not be the most optimal solution.)

Answer 2

You can define "shift" recursively: shift 0 is a no-op, shift 1+n (x:xs) is shift n xs.

Something like:

shift 0 = \x -> x
shift n = \lst@(x:xs) -> (shift (n-1) xs)

-- example:
sh3 = shift 3        

Then the 'rotate' problem becomes easier:

rotate n = \lst -> (shift lst) ++ (take n lst)