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.

Abstract:

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*

## Recent comments

1 day 14 hours ago

1 day 23 hours ago

2 days 51 min ago

2 days 1 hour ago

2 days 1 hour ago

2 days 3 hours ago

2 days 4 hours ago

2 days 9 hours ago

2 days 23 hours ago

3 days 11 min ago