Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875165 | Science of Computer Programming | 2018 | 33 Pages |
Abstract
Incremental computing is a method of maintaining consistency between an input and output. If only a small portion of the input is modified, it is natural to expect that the corresponding output can be obtained more efficiently than full re-computation. However, for nontrivial data structures, such as self-balancing binary search trees, even the most primitive modifications may lead to drastic change of the underlying structure. In this paper, we develop an method of incremental computing on data structures that may consist of complex modifications. The key idea is to use shortcut fusion in order to decompose a complex modification to a series of simple ones. Based on this idea, we extend Jeuring's incremental computing method on algebraic data structures to one on more complex data structures. The method is purely functional and does not rely on any run-time support. Its correctness is straightforward from parametricity. Moreover, its cost is often proportional to that of the corresponding modification.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Akimasa Morihata,