F# function to find all rotations of a list

Question

I have some F# code here for a recursive function that rotates a list to the left by n places. I am very new to F# and I'm looking for a way to modify this code to output not just one rotation by n positions, but all possible rotations.

For example, say I have the list:

let list1 = [1; 2; 3; 4]

I want to call rotate on this list such that the output is:

[ [1; 2; 3; 4]; [2; 3; 4; 1]; [3; 4; 1; 2]; [4; 1; 2; 3] ]

The code I have that does a left shift by n is:

let rec rotate xs k = 
    match xs, k with
        |[], _ -> []
        |xs, 0 -> xs
        |x::xs, k when k > 0 -> rotate(xs @ [x])(k-1)
        |xs, k -> rotate xs (List.length xs + k)

I'm not sure how to edit this to do the steps listed above. Any help or resources would be appreciated. I should add that I really want to function to be recursive. Thanks.

Answer 1

If I understand the question correctly, you can also write the function using the built-in List.permute function:

let rotate xs =
    let length = xs |> List.length
    let perm n = xs |> List.permute (fun index -> (index + n) % length) 
    [1 .. length] |> List.rev |> List.map perm

Example output (slightly formatted for improved readability):

> [1 .. 4] |> rotate;;
val it : int list list =
  [[1; 2; 3; 4];
   [2; 3; 4; 1];
   [3; 4; 1; 2];
   [4; 1; 2; 3]]

Answer 2

I would start off with making an infinite cyclic sequence off your original list. And then use List.init to get all the rotations.

let rotations list = 
    let rec cyclic sequence = seq {
        yield! sequence
        yield! cyclic sequence }
    let cyclic = cyclic list
    let length = List.length list
    List.init length (fun i -> cyclic |> Seq.skip i |> Seq.take length |> List.ofSeq)

the important thing is, that the sequence is lazy and therefore can be infinite.

Answer 3

Using the rotate function you already wrote:

let rotations xs = List.init (List.length xs) (rotate xs) 

By the way, you can shorten your rotate function to this:

let rec rotate xs k = 
    match xs, k with
        |[], _ -> []
        |xs, 0 -> xs
        |x::xs, k -> rotate (xs @ [x]) (k-1)

Patterns are matched top-down, so the guard when k > 0 is not necessary. The last line of your original solution would never match, so I removed it.

Answer 4

Since I wanted to do this specific question using recursion and matchings, I managed to figure it out and this is what I came up with:

let rotate xs =
    let n = List.length xs
    let rec rotation xs n = 
        match xs, n with
        |[], _ -> []
        |xs, 0 -> xs
        |x::xs, n -> rotation (xs @ [x]) (n-1)

    let rec rotateList xs n = //we are compiling a list of different rotations
        match xs, n with
        |xs, 0 -> [] 
        |xs, n -> (rotation xs ((List.length xs)-n))::rotateList xs (n-1)
    rotateList xs n 

I also specifically wanted only one input parameter, namely the list