[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Write this accumuator in a functional style

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

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