All list rotations in Haskell

Question

I have a function to rotate the list:

rotate :: [a] -> [a] rotate [] = [] rotate (x:xs) = xs ++ [x] 

Now I want a function that gives a list with every possible rotation of the final list:

 rotateAll :: [a] -> [[a]] 

In an 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, rational thinking probably does not help me find a functional solution to this problem. I am looking for some tips on how to deal with this.

Additional thoughts:

To solve this problem, I have two questions. First I need to rotate the list many times and collect each result into a list. So the first solution is to do something like

 rotateAll xs = [xs (rotate xs) (rotate (rotate xs)) (rotate (rotate (rotate xs))) ...] 

Of course, I do not know how many times to do this. I would be pleased to do this endlessly, and then use take (length xs) to get the finite number of lists I wish. This actually demonstrates a second problem: determining when to stop. I don't know if using take most efficient or elegant way to solve a problem, but it occurred to me when I was typing this and should work.

Addendum: Now that I have found two solutions on my own or with tips. I am pleased to welcome any other solutions that are faster or use different approaches. Thanks!

Answer 1

Besides iterate , you can write a function that generates a list of n turns. The case n = 0 would simply wrap the entry in the list, and the case n = m + 1 would add the input to the result of case m. While using standard features is usually preferable, sometimes writing your own solutions is great.

Answer 2

Use the predefined functions in Data.List ! You can get a list of all rotations with four function calls, without recursion and without the rotate function.

You asked not to offer a complete solution. For those who want to see this, a complete solution (one line of code) appears at http://pastebin.com/atGiw1ig .

Answer 3

Here is a version that is lazy both in the list of turns and in each individual entry in the list. The key is that instead of pre-calculating the length, simply map the items in your result to the items in the list when you go, stopping when the input list ends.

 rotations xs = map (takeSame xs) $ takeSame xs (tails (xs ++ xs)) where takeSame [] _ = [] takeSame (_:xs) (y:ys) = y:takeSame xs ys 

In addition, it is much better compared to some other options due to the use of tails and only for one concatenation. Of course, it also handles endless lists correctly.

Answer 4

You can also consider this site. How to define a rotates function that answers the same question.

Edit due to comment: inits based inits , as well as inits and tails based inits should be quadratic in the length of the list. However, one that is based on inits and tails should be less efficient as it performs several quadratic traversals. Although, note that these statements are only true if you fully evaluate the result. In addition, the compiler can improve the code, so you should be careful about these statements.

Answer 5

 rotations (x:xs) = (xs++[x]):(rotations (xs++[x]) ) 

this creates long lazy rotations now just take the first unique ones that will be equal to the length of the original list

 take (length xs) (rotations xs) 

Answer 6

I came up with two solutions. At first it’s a manual work that came to me after I posted my question:

 rotateAll :: [a] -> [[a]] rotateAll xs = rotateAll' xs (length xs) where rotateAll' xs 1 = [xs] rotateAll' xs n = xs : rotateAll' (rotate xs) (n - 1) 

Another uses @Tilo's suggestion:

 rotateAll :: [a] -> [[a]] rotateAll xs = take (length xs) (iterate rotate xs) 

Answer 7

You can also generate them recursively. Generating all rotations of an empty or single list of elements is trivial, and generating rotations x:xs is to insert x into the correct position for all rotations of xs .

You can do this by creating indexes to insert (just a list [1, 2, ...] if previous rotations are in that order) and use zipWith to insert x at the correct positions.

Alternatively, you can split rotate around a position using a combination of inits and tails and use zipWith to glue them together.

Answer 8

Addendum: Now that I have found two solutions on my own or with tips. I am pleased to welcome any other solutions that are faster or use different approaches. Thanks!

Since no one pointed out using cycle , I thought I would add this solution for the final lists:

 rotations x = let n = length x in map (take n) $ take n (tails (cycle x)) 

For an infinite list x rotations are just tails x .

The cycle x estimate is the time and space O (n), each element from tails is O (1), and take n is O (n) time and space, but two take n nested so evaluating the whole result O (n ^ 2) time and space.

If garbage collects each rotation before the lazy creation of the next, then space is theoretically O (n).

If you are smart about how much you consume, you do not need map (take n) and you can just go through cycle x or take n (tails (cycle x)) and save O (n) space.

Answer 9

From scratch:

 data [] a = [] | a : [a] end :: a -> [a] -> [a] end y [] = y : [] end y (x : xs) = x : y `end` xs -- such that `end x xs = xs ++ [x]` rotating :: [a] -> [[a]] rotating [] = [] rotating xs = rots xs where rots xs@ (x : xs') = xs : rots (x `end` xs') -- An infinite list of rotations rotations :: [a] -> [[a]] rotations xs = rots xs (rotating xs) where rots [] _ = [] rots (_ : xs) (r : rs) = r : rots xs rs -- All unique rotations, `forall xs.` equivalent to `take -- (length xs) (rotating xs)` 

Or:

 {-# LANGUAGE BangPatters #-} rotate :: [a] -> [a] rotate [] = [] rotate (x : xs) = x `end` xs where end y [] = y : [] end y (x : xs) = x : end y xs iterate :: Int -> (a -> a) -> a -> [a] iterate 0 _ _ = [] iterate nfx = case fx of x' -> x' : iterate (n - 1) fx' length :: [a] -> Int length xs = len 0 xs where len !n [] = n len !n (_ : xs) = len (n + 1) xs rotations :: [a] -> [[a]] rotations xs = iterate (length xs) rotate xs -- Starting with single rotation 

Or, integrated:

 rotations :: [a] -> [[a]] rotations [] = [[]] rotations xs = rots xs xs where rots [] _ = [] rots (_ : xc) xs@ (x : xs') = xs : rots xc (x `end` xs') end y [] = y : [] end y (x : xs) = x : end y xs 

Answer 10

Maybe you can use Data.List

 import Data.List rotate x=[take (length x) $ drop i $ cycle x | i<-[0..length x-1]] 

Answer 11

I used the following rotations function as an assistant for my permutation algorithm . It seems to be the fastest among all here.

 rotations :: [a] -> [[a]] rotations xs = take (length xs) (iterate (\(y:ys) -> ys ++ [y]) xs)