69 people like it.

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: 
 93: 
 94: 
 95: 
 96: 
 97: 
 98: 
 99: 
100: 
101: 
102: 
103: 
104: 
105: 
106: 
107: 
108: 
109: 
110: 
111: 
112: 
113: 
114: 
115: 
116: 
117: 
118: 
119: 
120: 
121: 
122: 
123: 
124: 
125: 
126: 
127: 
128: 
129: 
130: 
131: 
132: 
133: 
134: 
135: 
136: 
137: 
138: 
139: 
140: 
141: 
142: 
143: 

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

module List =
    /// Takes elements into a sublist until the predicate returns false (exclusive)
    let partitionWhile (func : _ -> bool) (sequence : _ seq) : _ list * _ list = 
        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 = 
            [
                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 * _ list = 
        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 = 
            [
                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 * _ list = 
        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 = 
            [
                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)
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 partitionWhile : func:('a -> bool) -> sequence:seq<'a> -> 'a list * 'a list

Full name: Script.List.partitionWhile


 Takes elements into a sublist until the predicate returns false (exclusive)
val remainder : 'a list
val partitionUntil : func:('a -> bool) -> sequence:seq<'a> -> 'a list * 'a list

Full name: Script.List.partitionUntil


Takes elements into a sublist until the predicate returns true (exclusive)
val partitionUntilAfter : func:('a -> bool) -> sequence:seq<'a> -> 'a list * 'a list

Full name: Script.List.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 )

More information

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

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.