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

13 hours 54 min ago

14 hours 10 min ago

18 hours 14 min ago

18 hours 43 min ago

19 hours 25 min ago

21 hours 28 min ago

23 hours 50 min ago

1 day 7 hours ago

1 day 8 hours ago

1 day 16 hours ago