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 hour 43 min ago
2 hours 12 min ago
9 hours 30 min ago
11 hours 29 min ago
13 hours 14 min ago
17 hours 28 min ago
17 hours 44 min ago
17 hours 51 min ago
18 hours 2 min ago
18 hours 13 min ago