1 people like it.
Like the snippet!

Rotate or shift lists

This rotates or shifts a list. Unlike http://www.fssnip.net/qY/title/Rotate-List, which runs exponentially, this runs at O(n). In case of overflow (i.e., shift index is larger than the size of the list) will run at most once more with the modulo. This is done to prevent using `List.length` prior to entering the function, as that would lead to a perf punishment of an extra O(n) on each invocation. For large lists, `shift largeList 1` would then get a big performance hit.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40:

let shift l i =
    let rec shiftInternal la lb len j =
        match lb with
        | [] -> 
            if j > 0 then 
                // we're rotating further than the size of the list
                // so let's continue with the modulo and run again
                let lb = List.rev la
                shiftInternal List.empty lb 0 (i % len )
            else
                // j = 0
                List.rev la

        | hd::tail when j > 0 -> shiftInternal (hd::la) tail (len + 1) (j - 1)
        | _ -> lb @ List.rev la

    if i > 0 then
        shiftInternal List.empty l 0 i
    elif i = 0 then
        l
    else
        // invalid input
        List.empty


// Running this:
// > shift [1;2;3;4;5;6;7] 13;;
// val it: int list = [7; 1; 2; 3; 4; 5; 6]
// 
// > shift [1;2;3;4;5;6;7] 14;;
// val it: int list = [1; 2; 3; 4; 5; 6; 7]
// 
// > shift [1;2;3;4;5;6;7] 2;;
// val it: int list = [3; 4; 5; 6; 7; 1; 2]
// 
// > shift [1;2;3;4;5;6;7] 7;;
// val it: int list = [1; 2; 3; 4; 5; 6; 7]
// 
// > shift [1;2;3;4;5;6;7] 8;;
// val it: int list = [2; 3; 4; 5; 6; 7; 1]

val shift : l:'a list -> i:int -> 'a list

val l : 'a list

val i : int

val shiftInternal : ('b list -> 'b list -> int -> int -> 'b list)

val la : 'b list

val lb : 'b list

val len : int

val j : int

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
    interface IReadOnlyList<'T>
    interface IReadOnlyCollection<'T>
    interface IEnumerable
    interface IEnumerable<'T>
    member GetReverseIndex : rank:int * offset:int -> int
    member GetSlice : startIndex:int option * endIndex:int option -> 'T list
    member Head : 'T
    member IsEmpty : bool
    member Item : index:int -> 'T with get
    member Length : int
    ...

val rev : list:'T list -> 'T list

val empty<'T> : 'T list

val hd : 'b

val tail : 'b list

Previous Version Raw view Test code New version

More information

Link:	http://fssnip.net/87j
Posted:	2 years ago
Author:	Abel Braaksma
Tags:	algorithm , list , recursion , rotate , tail recursion , shift