Write this accumuator in a functional style

[Steve D'Aprano]

On Tue, 11 Jul 2017 04:58 pm, Chris Angelico wrote:

> On Tue, Jul 11, 2017 at 4:11 PM, Steven D'Aprano <steve at pearwood.info> wrote:
[...]
>> accumulator = {'blue': [], 'green': [], 'red': []}
>> for parrot in parrots:
>>     accumulator[parrot.colour].append(parrot)
[...]

> It's a partitioning filter. (Three way, not the usual two, but same
> same.) I've actually often wanted a quick way to write that - where
> you divide a list into two according to "passes predicate" vs "fails
> predicate". So if you find a really nice solution, I'm interested.

That is one of my colleague's complaints too: he says this is a common task and
there ought to be a built-in or at least std lib functional solution for it,
akin to map/filter/itertools.

Although I often say "not every two or three line function needs to be a
built-in", in this case I'm inclined to agree with him. Now that I have a name
for it, I am even more inclined to agree.

It's an N-way partitioning filter. My example shows only three, but the real
code we're using has more than that.

def partition(iterable, keyfunc=bool):
    accumulator = {}
    for item in iterable:
        accumulator.setdefault(keyfunc(item), []).append(item)
    return accumulator



Alternatives:

- itertools.groupby requires you to sort the entire input stream 
  before starting; that's expensive, O(N log N) rather than just O(N).

- Greg's dict comprehension version requires N+1 passes through the data, 
  one to convert to a list, and 1 per each possible key.

- Terry's solution scares me :-)

- Alain's solution appears to require list concatenation, which implies 
  that in the worst case this will be O(N**2).

Any other thoughts?



-- 
Steve
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.