Write this accumuator in a functional style

[Chris Angelico]

On Wed, Jul 12, 2017 at 7:52 PM, Paul Rubin <no.email at nospam.invalid> wrote:
> 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.

Is that actual O(log n), or amortized? If you build a tree by forever
inserting larger values (which can happen easily - imagine using a
dict to record hourly statistics, using time.time()//3600 as the key),
at some point it'll need to be rebalanced, which could at worst case
be O(n). But I could believe that it's amortized logarithmic, although
I can't myself prove that it is.

ChrisA