I don't know the correct terminology for asking this question, so I'll describe it with lots of words instead, bear with me.
Background, just so we're on the same page: Programs often contain caches - a time/memory tradeoff. A common programmer's mistake is to forget to update a cached value after changing one of its upstream sources/precedents. But the dataflow or FRP programming paradigm is immune to such mistakes. If we have a number of pure functions, and connect them together in a directed dependency graph, then nodes can have their output value cached and re-used until any of the function's inputs change. This system architecture is described in the paper Caching In Dataflow-Based Environments and in an imperative language it's more or less analogous to memoization.
Problem: When one of the inputs to a function do change, we still have to execute the function as a whole, throwing away its cached output and re-calculating from scratch. In many cases, this seems wasteful to me. Consider a simple example that generates a "top 5 whatever" list. The input data is an unsorted list of whatever. It's passed as input to a function that outputs a sorted list. Which in turn is input to a function that takes the first 5 items only. In pseudocode:
input = [5, 20, 7, 2, 4, 9, 6, 13, 1, 45] intermediate = sort(input) final_output = substring(intermediate, 0, 5)
The complexity of the sort function is O(N log N). But consider that this flow is used in an application where the input only changes a little bit at a time, by adding 1 element. Rather than re-sorting from scratch every time, it would be faster, in fact O(N), to use a function which updates the old cached sorted list by inserting the new element in the correct position. This is just one example - many "from scratch" functions have such "incremental update" counterparts. Also, maybe the newly added element won't even appear in the final_output because it's after the 5th position.
My intuition suggests it might be possible to somehow add such "incremental update" functions to a dataflow system, side by side with the existing "from scratch" functions. Of course, re-calculating everything from scratch must always give the same result as a doing bunch of incremental updates. The system should have the property that if each of the individual primitive FromScratch-Incremental pairs always give the same result, then the larger composite functions built from them should also automatically give the same result.
Question: Is it possible to have a system/architecture/paradigm/meta-algorithm which can support both FromScratch functions and their Incremental counterparts, cooperating for efficiency, and composed into large flows? If not, why? If someone has researched this paradigm already and published it, what is it called, and can I get a short summary of how it works?