Write this accumuator in a functional style

[Paul Rubin]

Steven D'Aprano <steve at pearwood.info> writes:
> for parrot in parrots:
>     accumulator[parrot.colour].append(parrot)
>
> That's pretty compact and understandable, but it require mutating a bunch 
> of pre-allocated lists inside an accumulator. Can we re-write this in a 
> functional style?

Not so easily in Python since the built-in list and dict types are
designed for mutation update.  In Haskell, the list type is a linked
list and the dictionary type is a balanced tree.  So, you can make a new
list consisting of a new item consed to the front of the old list, and
you can make a new ("updated") dictionary by building O(log n) new
nodes.

You might like Chris Okasaki's wonderful book "Purely Functional Data
Structures" that explains all this and more.