77 people like it.

# Split a list

Three ways to split a list in half (but not necessarily in the middle). A forth version added that's very short and should be fast, as we only use List.fold. New champ found.

 ``` 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: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: ``` ``````module List= (* Execution: fastest, Output: least intuitive *) let split s = let rec loop = function | (_,[],a,b) -> (a,b) | (true,h::t,a,b) -> loop(false,t,h::a,b) | (false,h::t,a,b)-> loop (true,t,a,h::b) in loop(true,s,[],[]) (* Execution: slowest, Output: most intuitive *) let split1 s = let len = List.length s in s |> List.mapi (fun i x -> (i List.partition fst |> (fun (x,y) -> ((x |> List.map snd),(y |> List.map snd))) (* Execution: average, Output: fairly intuitive *) let split2 s = let len = List.length s in s |> List.fold (fun (n,(a,b)) x -> (n+1,if n <(len/2) then (x::a,b) else (a,x::b))) (0,([],[])) |> snd (* Execution: quite fast, Output: short and elegant *) let split3 s = List.fold (fun (xs, ys) e -> (e::ys, xs)) ([], []) s Timing function let l = [1..10000000] printfn "%d" (timeit List.split l) printfn "%d" (timeit List.split1 l) printfn "%d" (timeit List.split2 l) printfn "%d" (timeit List.split3 l) (* Results: List.split: 1584ms List.split1: 4789ms List.split2: 4219ms List.split3: 2730ms *) (* > List.split [1..10];; val it : int list * int list = ([9; 7; 5; 3; 1], [10; 8; 6; 4; 2]) > List.split1 [1..10];; val it : int list * int list = ([1; 2; 3; 4; 5], [6; 7; 8; 9; 10]) > List.split2 [1..10];; val it : int list * int list = ([5; 4; 3; 2; 1], [10; 9; 8; 7; 6]) > List.split3 [1..10];; val it : int list * int list = ([10; 8; 6; 4; 2], [9; 7; 5; 3; 1]) > *) ``````
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val split : s:'a list -> 'a list * 'a list

Full name: Script.List.split
val s : 'a list
val loop : (bool * 'b list * 'b list * 'b list -> 'b list * 'b list)
val a : 'b list
val b : 'b list
val h : 'b
val t : 'b list
val split1 : s:'a list -> 'a list * 'a list

Full name: Script.List.split1
val len : int
val length : list:'T list -> int

Full name: Microsoft.FSharp.Collections.List.length
val mapi : mapping:(int -> 'T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.mapi
val i : int
val x : 'a
val partition : predicate:('T -> bool) -> list:'T list -> 'T list * 'T list

Full name: Microsoft.FSharp.Collections.List.partition
val fst : tuple:('T1 * 'T2) -> 'T1

Full name: Microsoft.FSharp.Core.Operators.fst
val x : (bool * 'a) list
val y : (bool * 'a) list
val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
val snd : tuple:('T1 * 'T2) -> 'T2

Full name: Microsoft.FSharp.Core.Operators.snd
val split2 : s:'a list -> 'a list * 'a list

Full name: Script.List.split2
val fold : folder:('State -> 'T -> 'State) -> state:'State -> list:'T list -> 'State

Full name: Microsoft.FSharp.Collections.List.fold
val n : int
val a : 'a list
val b : 'a list
val split3 : s:'a list -> 'a list * 'a list

Full name: Script.List.split3
val xs : 'a list
val ys : 'a list
val e : 'a
let timeit func param =
let sw = new System.Diagnostics.Stopwatch()
sw.Start()
let _, _ = func param
sw.Stop()
sw.ElapsedMilliseconds
val l : int list

Full name: Script.l
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
val timeit : func:('a -> 'b * 'c) -> param:'a -> int64

Full name: Script.timeit
Multiple items
module List

from Script

--------------------
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>