Memoization is an interesting technique that could be used to implement a purely functional spreadsheet, without the need of maintaining a dependency graph. I've written a small article on the subject.
There are many ways to implement incremental computation. One popular method - implemented by spreadsheets - is to keep an up-to-date topologically sorted dependency graph of all cells.
After modification of a cell, a spreadsheet can optimally determine which cells need to be recalculated (without recalculating everything) given its dependency graph.
In this short paper we will discuss another approach that is based on memoization.
An example is given that uses a divide and conquer algorithm to maximally re-use sums of integers. Next to that, we sketch a possible implementation based on uniquely represented confluently persistent treaps.
edit: small typo