1 people like it.

# 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 IEnumerable
interface IEnumerable<'T>
member GetReverseIndex : rank:int * offset:int -> int
member GetSlice : startIndex:int option * endIndex:int option -> 'T list