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.

Copy Source
Copy Link
Tools:
 1: module List=
 2:     (* Execution: fast, Output: least intuitive *)
 3:     let split s = 
 4:         let rec loop = function
 5:         | (_,[],a,b) -> (a,b)
 6:         | (true,h::t,a,b) -> loop(false,t,h::a,b)
 7:         | (false,h::t,a,b)-> loop (true,t,a,h::b)
 8:         in loop(true,s,[],[])
 9:     (* Execution: slowest, Output: most intuitive *)
10:     let split1 s =
11:         let len = List.length s in
12:         s |> List.mapi (fun i x -> (i<len/2,x))
13:           |> List.partition fst
14:           |> (fun (x,y) -> ((x |> List.map snd),(y |> List.map snd)))
15:     (* Execution: average, Output: fairly intuitive *)
16:     let split2 s =
17:          let len = List.length s in
18:          s |> List.fold (fun (n,(a,b)) x -> 
19:             (n+1,if n <(len/2) then (x::a,b) else (a,x::b)))
20:                   (0,([],[]))
21:            |> snd
22:     (* Execution: quite fast, Output: short and elegant *)
23:     let split3 s = List.fold (fun (xs, ys) e -> (e::ys, xs)) ([], []) s
24:     (* Execution: fastest, Output: fairly intuitive, but inner function needed *)
25:     let split4 s =
26:         let rec loop l (xs, ys) =
27:             match l with
28:             | x::y::rest -> loop rest (x::xs, y::ys)
29:             | [x] -> (x::xs, ys)
30:             | _ -> (xs, ys)
31:         loop s ([], [])
32:             
33: 
34: Timing function
35: 
36: let l = [1..10000000]
37: 
38: printfn "%d" (timeit List.split l)
39: printfn "%d" (timeit List.split1 l)
40: printfn "%d" (timeit List.split2 l)
41: printfn "%d" (timeit List.split3 l)
42: printfn "%d" (timeit List.split4 l)
43: 
44: (*
45: Results:
46: List.split:  1234ms
47: List.split1: 5242ms
48: List.split2: 3235ms
49: List.split3: 2754ms
50: List.split4: 1068ms
51: *)
52: 
53: (*
54: > List.split [1..10];;
55: val it : int list * int list = ([9; 7; 5; 3; 1], [10; 8; 6; 4; 2])
56: > List.split1 [1..10];;
57: val it : int list * int list = ([1; 2; 3; 4; 5], [6; 7; 8; 9; 10])
58: > List.split2 [1..10];;
59: val it : int list * int list = ([5; 4; 3; 2; 1], [10; 9; 8; 7; 6])
60: > List.split3 [1..10];;
61: val it : int list * int list = ([10; 8; 6; 4; 2], [9; 7; 5; 3; 1])
62: > List.split4 [1..10];;
63: val it : int list * int list = ([9; 7; 5; 3; 1], [10; 8; 6; 4; 2])
64: > 
65: *)
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------

type List<'T> =
  | ( [] )
  | ( :: ) of 'T * 'T list
  with
    interface System.Collections.IEnumerable
    interface System.Collections.Generic.IEnumerable<'T>
    member Head : '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
  end

Full name: Microsoft.FSharp.Collections.List<_>

  type: List<'T>
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'T>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'T>
  implements: System.Collections.IEnumerable
val split : 'a list -> 'a list * 'a list

Full name: Snippet.List.split
val s : 'a list

  type: 'a list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'a>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'a>
  implements: System.Collections.IEnumerable
val loop : (bool * 'b list * 'b list * 'b list -> 'b list * 'b list)
val a : 'b list

  type: 'b list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'b>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'b>
  implements: System.Collections.IEnumerable
val b : 'b list

  type: 'b list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'b>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'b>
  implements: System.Collections.IEnumerable
val h : 'b
val t : 'b list

  type: 'b list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'b>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'b>
  implements: System.Collections.IEnumerable
val split1 : 'a list -> 'a list * 'a list

Full name: Snippet.List.split1
val len : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType
val length : 'T list -> int

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

Full name: Microsoft.FSharp.Collections.List.mapi
val i : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType
val x : 'a
val partition : ('T -> bool) -> 'T list -> 'T list * 'T list

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

Full name: Microsoft.FSharp.Core.Operators.fst
val x : (bool * 'a) list

  type: (bool * 'a) list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<bool * 'a>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<bool * 'a>
  implements: System.Collections.IEnumerable
val y : (bool * 'a) list

  type: (bool * 'a) list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<bool * 'a>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<bool * 'a>
  implements: System.Collections.IEnumerable
val map : ('T -> 'U) -> 'T list -> 'U list

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

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

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

Full name: Microsoft.FSharp.Collections.List.fold
val n : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType
val a : 'a list

  type: 'a list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'a>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'a>
  implements: System.Collections.IEnumerable
val b : 'a list

  type: 'a list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'a>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'a>
  implements: System.Collections.IEnumerable
val split3 : 'a list -> 'a list * 'a list

Full name: Snippet.List.split3
val xs : 'a list

  type: 'a list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'a>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'a>
  implements: System.Collections.IEnumerable
val ys : 'a list

  type: 'a list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'a>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'a>
  implements: System.Collections.IEnumerable
val e : 'a
val split4 : 'a list -> 'a list * 'a list

Full name: Snippet.List.split4
val loop : ('b list -> 'b list * 'b list -> 'b list * 'b list)
val l : 'b list

  type: 'b list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'b>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'b>
  implements: System.Collections.IEnumerable
val xs : 'b list

  type: 'b list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'b>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'b>
  implements: System.Collections.IEnumerable
val ys : 'b list

  type: 'b list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'b>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'b>
  implements: System.Collections.IEnumerable
val x : 'b
val y : 'b
val rest : 'b list

  type: 'b list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'b>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'b>
  implements: System.Collections.IEnumerable
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: Snippet.l

  type: int list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<int>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<int>
  implements: System.Collections.IEnumerable
val printfn : Printf.TextWriterFormat<'T> -> 'T

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

Full name: Snippet.timeit
Multiple items
module List

from Snippet

--------------------

module List

from Microsoft.FSharp.Collections

--------------------

type List<'T> =
  | ( [] )
  | ( :: ) of 'T * 'T list
  with
    interface System.Collections.IEnumerable
    interface System.Collections.Generic.IEnumerable<'T>
    member Head : '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
  end

Full name: Microsoft.FSharp.Collections.List<_>

  type: List<'T>
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<'T>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<'T>
  implements: System.Collections.IEnumerable

More information

Link: http://fssnip.net/3h
Posted: 3 years ago
Author: Dmitri Pavlenkov
Tags: list, split, recursion, fold, partition, match