Lambda the Ultimate

I hope someone can point me to literature regarding theories of 'incremental' calculation. Many people here will know about folds or catamorphisms and how they help with computations on lists. I am trying to understand the theories of similar calculations when items are added to lists. For example, it is one thing to calculate a sum of integers in a list, but what about returning the sum each time a new integer is added? Or to make it a little more tricky, how does one effeciently (and generically) calculate an average of integers in a list...when integers are being constantly being added?

Actually I found this paper: Incremental algorithms on lists by Johan Jeuring, it has a chapter on incremental algorithms...but I can't understand one word. I didn't understand Functional Programming with Bananas, Lenses, Envelopes, and Barbed Wire until I read some introductory material on foldr (I still don't understand it completely). I'm hoping there are more basic references which will help me understand incremental algorithms (or would it be right to call them incremental folds). Thanks!

I just want to ask the rather naive question: Why are lists the most popular builtin aggregate data structure in FP langs? I understand the historical precedent for lists, and I understand that lists are very well understood. But really, there is nothing magical about lists, and computationally, they aren't particularly cheap. It seems to me that the basic interface lists provide that FP consumes is head(), rest(), append(), and splice(). There may be a few others, but my point is that there are lots of data structures that can support this interface. So why not make the interface intrinsic, rather than the data structure, and support lots of different structures intrisically (arrays and trees come to mind)?