Data.Sequence.Util

Documentation

splitMonotone :: (a -> Bool) -> Seq a -> (Seq a, Seq a)

Partition the seq s given a monotone predicate p into (xs,ys) such that

all elements in xs do *not* satisfy the predicate p all elements in ys do satisfy the predicate p

all elements in s occur in either xs or ys.

running time: \(O(\log^2 n + T*\log n)\), where \(T\) is the time to execute the predicate.