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 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

More information

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