I have a function to rotate a list:
rotate :: [a] -> [a]
rotate [] = []
rotate (x:xs) = xs ++ [x]
Now I want a function that gives a list with every possible rotation of a finite list:
rotateAll :: [a] -> [[a]]
In a imperative language, I would do something like (in pseudocode)
for i = 1 to length of list
append list to rotateList
list = rotate(list)
Of course, thinking imperatively probably doesn't help me find a functional solution to this problem. I'm looking for some hints as to how to tackle this.
Additional thoughts:
To solve this, I have two issues to tackle. First I need to repeatedly rotate a list and collect each result into a list. So a first solution needs to do something like
rotateAll xs = [xs (rotate xs) (rotate (rotate xs)) (rotate (rotate (rotate xs))) ...]
Of course I don't know how many times to do this. I'd be satisfied to do this infinitely and then use take (length xs)
to get the finite number of lists I desire. This actually demonstrates the second issue: determining when to stop. I don't know if using take
is the most efficient or elegant way to solve the problem, but it came to mind as I was typing this and should work.
Addendum: Now that I have found two solutions on my own or with hints. I will gladly welcome any other solutions that are faster or use different approaches. Thanks!