NYFPN Reading Group

Incremental Algorithms on Lists
Johan Jeuring
http://citeseer.ist.psu.edu/6782.html
Incremental computations can improve the performance of interactive programs such as spreadsheet programs, program development environments, text editors, etc. Incremental algorithms describe how to compute a required value depending on the input, after the input has been edited. By considering the possible different edit actions on the data type lists, the basic data type used in spreadsheet programs and text editors, we define incremental algorithms on lists. Some theory for the construction...

Adaptive Functional Programming
Umut A. Acar, Guy E. Blelloch, and Robert Harper
http://ttic.uchicago.edu/~umut/papers/toplas06.html
We present techniques for incremental computing by introducing adaptive functional programming. As an adaptive program executes, the underlying system represents the data and control dependences in the execution in the form of a dynamic dependence graph . When the input to the program changes, a change propagation algorithm updates the output and the dynamic dependence graph by propagating changes through the graph and re-executing code where necessary. Adaptive programs adapt their output to any change in the input, small or large.

There and Back Again: Arrows for Invertible Programming
Artem Alimarine, Sjaak Smetsers, Arjen van Weelden, Marko van Eekelen, Rinus Plasmeijer
http://citeseer.ist.psu.edu/alimarine05there.html
Invertible programming occurs in the area of data conversion where it is required that the conversion in one direction is the inverse of the other. For that purpose, we introduce bidirectional arrows (bi- arrows). The bi-arrow class is an extension of Haskell's arrow class with an extra combinator that changes the direction of computation. The advantage of the use of bi-arrows for invertible programming is the preservation of invertibility properties using the biarrow combinators

The essence of Dataflow Programming
Tarmo Uustalu and Varmo Vene
http://lambda-the-ultimate.org/node/988
We propose a novel, comonadic approach to dataflow (streambased) computation. This is based on the observation that both general and causal stream functions can be characterized as coKleisli arrows of comonads and on the intuition that comonads in general must be a good means to structure context-dependent computation. In particular, we develop a generic comonadic interpreter of languages for context-dependent computation and instantiate it for stream-based computation. We also discuss distributive laws of a comonad over a monad as a means to structure combinations of effectful and context-dependent computation. We apply the latter to analyse clocked dataflow (partial streams based) computation.