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

You seem to prefer that we fix your code than start again, so let's have a look at your code. Firstly, the main list chopping:

reverse (take i (reverse xs)) ++ reverse (drop i (reverse xs)) 

Now reverse (take i (reverse xs)) takes i elements from the end of the list, but you reverse the list twice to achieve this, and it would be better to do drop (length xs - i) xs. Similarly, you can implement reverse (drop i (reverse xs))) as take (length xs - i) xs. That gives us

drop (length xs - i) xs ++ take (length xs - i) xs 

Now your code \i->[1..n]<=n doesn't make sense because it compares the list [1..n] with n, which can't work. I think you're trying to make a loop where i runs from 1 to n, which is a good plan. Let's use a list comprehension to get the ones we wanted:

[drop (length xs - i) xs ++ take (length xs - i) xs | i <- [1 .. length xs], i <= n]

but now we're running from 1 to the length of the list but throwing away numbers above n, which would be better written

[drop (length xs - i) xs ++ take (length xs - i) xs | i <- [1..n]]

This does allow n to be more than length xs, but I don't see a big issue there, we could check that at first.

Notice now that we're only using i in the form (length xs - i), and really we're recalculating length xs an awful lot more than we should, so instead of letting i run from 1 to n, and using length xs - i, why don't we just have j=length xs -i so j runs from length xs to length xs - n:

[drop j xs ++ take j xs | j <- [length xs,length xs - 1 .. length xs - n]]

which works because for example [6,5..1] == [6,5,4,3,2,1]

It would be neater to do

let l = length xs in
  [drop j xs ++ take j xs | j <- [l,l - 1 .. l - n]]

or maybe you like to take more than you like to do arithmetic, so we could use:

let l = length xs in
  take n [drop j xs ++ take j xs | j <- [l,l - 1 .. 0]]

which has the added benefit of stopping you doing too many, stopping you when you get back to the start.

I'd rename your function from generatingListforRightShifting to rotationsR, giving

rotationsR n xs = let l = length xs in
  take n [drop j xs ++ take j xs | j <- [l,l - 1 ..]]

Which gives rotationsR 6 [1..4] == [[1,2,3,4],[4,1,2,3],[3,4,1,2],[2,3,4,1],[1,2,3,4]].

Left rotation would look simpler:

rotationsL n xs = take n [drop j xs ++ take j xs | j <- [0..length xs]]

---

Digression: I couldn't help myself, sorry, and I started again.

I still don't like all that dropping and taking every single time, I'd rather pop infinitely many copies of xs next to each other (cycle xs) and take infinitely many tails of that, chopping them all to the right length, but just give you the first n:

rotationsL' n xs = let l = length xs in take n . map (take l) . tails . cycle $ xs

Because of lazy evaluation, only a finite amount of cycle xs ever gets calculated, but this one can run and run: rotationsL' 10 [1..4] gives you:

 [[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3],[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3],[1,2,3,4],[2,3,4,1]]

It would be nice to do the right roations that way too, but it doesn't work because I'd need to start at the end of an infinite list and work my way back. Let's reuse your reverse, take what you need, reverse trick again, though:

rotationsR' n xs = let l = length xs in
  take n . map (reverse.take l) . tails . cycle . reverse $ xs

---

Undigression: If you'd rather stick more closely to your original code, you can do

generatingListforRightShifting n xs = 
    [reverse (take i (reverse xs)) ++ reverse (drop i (reverse xs)) | i <- [1..n]]

Answer 2

I find a left rotation to be very straight forward using splitAt:

import Data.Tuple (swap)
rotateLeft n = uncurry (++) . swap . splitAt n

> rotateLeft 2 "Hello World!"
>>> "llo World!He"

Answer 3

Using cycle here seems nice:

shifts n xs = take (n+1) $ shifts' (cycle xs)
  where
    len = length xs
    shifts' ys = take len ys:shifts' (drop (len-1) ys)

Answer 4

I would drop the current approach, which is very convoluted. Instead, focus on abstracting the different components of the operation. If you break the operation into parts, you will notice that there are two symmetric components: rotating the list to the left, and rotating the list to the right. The operation you wish to define iterates the right rotation a specified number of times over some list. This suggests that the desired operation can be defined by taking a specified number of iterations of either the left or right rotation. For example,

left :: [a] -> [a]
left [] = []
left xs = tail xs ++ [head xs]

right :: [a] -> [a]
right [] = []
right xs = last xs : init xs

shiftL :: Int -> [a] -> [[a]]
shiftL n = take n . iterate left

shiftR :: Int -> [a] -> [[a]]
shiftR n = take n . iterate right

Answer 5

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)

Answer 6

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