Haskell - feeding back the result of a function to itself n times

Question

I'm trying to write a function that takes the last element of a list and puts that element in front of the list. I need this function to run an n amount of times.

The function, that does the flipping.

flipBack' :: [a] -> [a]
flipBack' xs = [last xs] ++ reverse (drop 1 (reverse xs))

So the above is like a helper function for the lower one, which takes in the initial string and the number of times that it needs the above function to run.

rotate :: String -> Int -> String
rotate xs n =  flipBack' xs

So for example if n is 3 then the rotate function should do the following:

flipBack'(flipBack'(flipBack' xs))

It seems like iterate should be used here somehow, but I am having trouble implementing it here, because I don't fully understand how it works.

Answer 1

This is not a good way to implement the rotate function! flipBack' is O(length xs), and you're iterating it; this is terribly expensive. How can you do better?

One way: do arithmetic

First, note that performing flipBack' length xs times gives you back xs. So you can start by reducing n.

rotate n xs = rotate' (lenx - n `mod` lenx) xs where
   lenx = length xs

Ok, so now how do we rotate'? By splitting!

rotate' shift xs = end ++ beginning where
  (beginning, end) = splitAt shift xs

Make things lazy

If n is much smaller than the length of the list, the above approach of traversing the list to get the length before actually producing anything is unfortunate. If that's likely to be the case, it's likely better to traverse the list with a simplified queue. This approach is too complicated for me to code blindly on my phone, so I'll just leave it as an idea to think about.

Answer 2

the function you're looking for is iterate

e.g.

> (iterate flipBack' [1..3])!!3
[1,2,3]

so you can write

rotate xs n = (iterate flipBack' xs)!!n

note that iterate is very easy to define yourself as well

iterate f x =  x : iterate f (f x)