69 people like it.
Like the snippet!

Partition a sequence until a predicate is satiated

This function is given a partition predicate and a sequence. Until the predicate returns false, a list will be filled with elements. When it is, both the list and the remainder of the sequence will be returned. Note that this example preserves the laziness of the unchecked sequence elements.

 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: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 
64: 
65: 
66: 
67: 
68: 
69: 
70: 
71: 
72: 
73: 
74: 
75: 
76: 
77: 
78: 
79: 
80: 
81: 
82: 
83: 
84: 
85: 
86: 
87: 
88: 
89: 
90: 
91: 
92:

module Seq =
    /// Takes elements into a sublist until the predicate returns false (exclusive)
    let partitionWhile (func : _ -> bool) (sequence : _ seq) : _ list * _ seq = 
        let en = sequence.GetEnumerator ()
        let wasGood = ref true
        let sublist = 
            [
                while !wasGood && en.MoveNext() do
                    if func en.Current then yield en.Current
                    else wasGood := false
            ]
        let remainder = 
            seq { 
                    if not !wasGood then yield en.Current
                    while en.MoveNext() do yield en.Current 
                }
        sublist, remainder

    ///Takes elements into a sublist until the predicate returns true (exclusive)
    let partitionUntil (func : _ -> bool) (sequence : _ seq) : _ list * _ seq = 
        let en = sequence.GetEnumerator ()
        let satisfied = ref false
        let sublist = 
            [
                while not !satisfied && en.MoveNext() do
                    if not (func en.Current) then yield en.Current
                    else satisfied := true
            ]
        let remainder = 
            seq { 
                    if !satisfied then yield en.Current
                    while en.MoveNext() do yield en.Current 
                }
        sublist, remainder

    ///Takes elements into a sublist until the predicate returns true (inclusive)
    let partitionUntilAfter (func : _ -> bool) (sequence : _ seq) : _ list * _ seq = 
        let en = sequence.GetEnumerator ()
        let satisfied = ref false
        let sublist = 
            [
                while not !satisfied && en.MoveNext() do
                    if func en.Current then satisfied := true
                    yield en.Current
            ]
        let remainder = 
            seq { 
                    while en.MoveNext() do yield en.Current 
                }
        sublist, remainder

[<Fact>]
let ``Seq.partitionWhile should return a proper subset and remainder`` () =
    let testSeq = seq { for i in 1 .. 6 do yield i }
    let sub, remainder = testSeq |> Seq.partitionWhile (fun x -> x <= 3)
    Assert.Equal( [1; 2; 3], sub )
    Assert.Equal( [4; 5; 6], remainder |> Seq.toList )

[<Fact>] 
let ``Seq.partitionWhile should return an empty list and remainder when give an empty sequence`` () =
    let testSeq = Seq.empty
    let sub, remainder = testSeq |> Seq.partitionWhile (fun x -> x <= 3)
    Assert.Empty sub
    Assert.Empty remainder

[<Fact>]
let ``Seq.partitionUntil should return a proper subset and remainder`` =
    let testSeq = seq { for i in 1 .. 6 do yield i }
    let sub, remainder = testSeq |> Seq.partitionUntil (fun x -> x > 3)
    Assert.Equal( [1; 2; 3], sub )
    Assert.Equal( [4; 5; 6], remainder |> Seq.toList )

[<Fact>] 
let ``Seq.partitionUntil should return an empty list and remainder when give an empty sequence`` () =
    let testSeq = Seq.empty
    let sub, remainder = testSeq |> Seq.partitionUntil (fun x -> x > 3)
    Assert.Empty sub
    Assert.Empty remainder

[<Fact>]
let ``Seq.partitionUntilAfter should return a proper subset and remainder`` () =
    let testSeq = seq { for i in 1 .. 6 do yield i }
    let sub, remainder = testSeq |> Seq.partitionUntilAfter (fun x -> x > 2)
    Assert.Equal( [1; 2; 3], sub )
    Assert.Equal( [4; 5; 6], remainder |> Seq.toList )

[<Fact>] 
let ``Seq.partitionUntilAfter should return an empty list and remainder when give an empty sequence`` () =
    let testSeq = Seq.empty
    let sub, remainder = testSeq |> Seq.partitionUntilAfter (fun x -> x > 2)
    Assert.Empty sub
    Assert.Empty remainder

module Seq

from Microsoft.FSharp.Collections

val partitionWhile : func:('a -> bool) -> sequence:seq<'a> -> 'a list * seq<'a>

Full name: Script.Seq.partitionWhile

Takes elements into a sublist until the predicate returns false (exclusive)

val func : ('a -> bool)

type bool = System.Boolean

Full name: Microsoft.FSharp.Core.bool

val sequence : seq<'a>

Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

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

type 'T list = List<'T>

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

val en : System.Collections.Generic.IEnumerator<'a>

System.Collections.Generic.IEnumerable.GetEnumerator() : System.Collections.Generic.IEnumerator<'a>

val wasGood : bool ref

Multiple items
val ref : value:'T -> 'T ref

Full name: Microsoft.FSharp.Core.Operators.ref

--------------------
type 'T ref = Ref<'T>

Full name: Microsoft.FSharp.Core.ref<_>

val sublist : 'a list

System.Collections.IEnumerator.MoveNext() : bool

property System.Collections.Generic.IEnumerator.Current: 'a

val remainder : seq<'a>

val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not

val partitionUntil : func:('a -> bool) -> sequence:seq<'a> -> 'a list * seq<'a>

Full name: Script.Seq.partitionUntil

Takes elements into a sublist until the predicate returns true (exclusive)

val satisfied : bool ref

val partitionUntilAfter : func:('a -> bool) -> sequence:seq<'a> -> 'a list * seq<'a>

Full name: Script.Seq.partitionUntilAfter

Takes elements into a sublist until the predicate returns true (inclusive)

val ( Seq.partitionWhile should return a proper subset and remainder ) : unit -> 'a

Full name: Script.( Seq.partitionWhile should return a proper subset and remainder )

val testSeq : seq<int>

val i : int

val sub : int list

val remainder : seq<int>

Multiple items
module Seq

from Script

--------------------
module Seq

from Microsoft.FSharp.Collections

val x : int

val toList : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.Seq.toList

val ( Seq.partitionWhile should return an empty list and remainder when give an empty sequence ) : unit -> 'a

Full name: Script.( Seq.partitionWhile should return an empty list and remainder when give an empty sequence )

val testSeq : seq<'b>

val empty<'T> : seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.empty

val ( Seq.partitionUntil should return a proper subset and remainder ) : obj

Full name: Script.( Seq.partitionUntil should return a proper subset and remainder )

val ( Seq.partitionUntil should return an empty list and remainder when give an empty sequence ) : unit -> 'a

Full name: Script.( Seq.partitionUntil should return an empty list and remainder when give an empty sequence )

val ( Seq.partitionUntilAfter should return a proper subset and remainder ) : unit -> 'a

Full name: Script.( Seq.partitionUntilAfter should return a proper subset and remainder )

val ( Seq.partitionUntilAfter should return an empty list and remainder when give an empty sequence ) : unit -> 'a

Full name: Script.( Seq.partitionUntilAfter should return an empty list and remainder when give an empty sequence )

Previous Version Raw view Test code New version

More information

Link:	http://fssnip.net/1I
Posted:	13 years ago
Author:	Rick Minerich
Tags:	seq , list , subset , partition