This post originated from an RSS feed registered with Python Buzz
by Thomas Guest.
Original Post: Group When
Feed Title: Word Aligned: Category Python
Feed URL: http://feeds.feedburner.com/WordAlignedCategoryPython
Feed Description: Dynamic languages in general. Python in particular. The adventures of a space sensitive programmer.
He later clarified what he was after — and had now found — linking to a solution posted a couple of years ago by Tomas Petricek. The function groupWhen splits a sequence into groups, starting a new group whenever the predicate holds.
module Seq =
/// Iterates over elements of the input sequence and groups adjacent elements.
/// A new group is started when the specified predicate holds about the element
/// of the sequence (and at the beginning of the iteration).
///
/// For example:
/// Seq.groupWhen isOdd [3;3;2;4;1;2] = seq [[3]; [3; 2; 4]; [1; 2]]
let groupWhen f (input:seq<_>) = seq {
use en = input.GetEnumerator()
let running = ref true
// Generate a group starting with the current element. Stops generating
// when it founds element such that 'f en.Current' is 'true'
let rec group() =
[ yield en.Current
if en.MoveNext() then
if not (f en.Current) then yield! group()
else running := false ]
if en.MoveNext() then
// While there are still elements, start a new group
while running.Value do
yield group() |> Seq.ofList }
Here’s a nice Haskell version coded up by @sdarlington.
Maybe takewhile and dropwhile could power a Python solution, but my first choice would be itertools.groupby. A suitable key function could just count the number of times the predicate holds.
class count_p:
''' Return a value which increments every time the predicate holds, starting from 0.
'''
def __init__(self, pred):
self._n = 0
self._pred = pred
def __call__(self, v):
self._n += self._pred(v)
return self._n
def group_when(pred, xs):
return (gp for _, gp in groupby(xs, count_p(pred)))
Here, group_when accepts an iterable and returns an iterable sequence of iterable groups. Clients choose how to consume the results.
>>> def odd(v): return v % 2
>>> xs = group_when(odd, [3, 3, 2, 4, 1, 2])
>>> print([list(g) for g in xs])
[[3], [3, 2, 4], [1, 2]]
Note that count_p does something very like itertools.accumulate. Here’s another version of group_when which takes advantage of this.
def group_when(pred, xs):
xs, ys = tee(xs)
accu = accumulate(map(pred, ys))
return (gp for _, gp in groupby(xs, lambda _: next(accu)))
Previous Topic
