83 people like it.
Like the snippet!

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:

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<len/2,x))
          |> 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

(*
> 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])
> 
*)

Multiple items
module List

from Microsoft.FSharp.Collections

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

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

Next Version Raw view Test code New version

More information

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