ComputingComputer ScienceAlgebraProgramming LanguagesTheory Of ComputationAbstract Syntax TreesFunctional ProgrammingType CheckingType SystemsIncremental ComputationMonadic SemanticsMonads
This paper presents a monadic approach to incremental computation, suitable for purely functional languages such as Haskell. A program that uses incremental computation is able to perform an incremental amount of computation to accommodate for changes in input data. Recently, Acar, Blelloch and Harper presented a small Standard ML library that supports efficient, high-level incremental computations [1]. Here, we present a monadic variant of that library, written in Haskell extended with first-class references. By using monads, not only are we able to provide a purely functional interface to the library, the types also enforce "correct usage" without having to resort to any type-system extension. We also find optimization opportunities based on standard monadic combinators.This is an exercise in putting to work monad transformers with environments, references, and continuations.
10
Report on the programming language Haskell
Paul Hudak, Simon Peyton Jones, Philip Wadler et al. · ACM SIGPLAN Notices · 1992 · 1K citations · Full text
The essence of functional programming
Philip Wadler · 1992 · 676 citations · Full text
Monad transformers and modular interpreters
Sheng Liang, Paul Hudak, Mark P. Jones · 1995 · 504 citations · Full text
Two algorithms for maintaining order in a list
Paul F. Dietz, Daniel D. Sleator · 1987 · 324 citations · Full text
Cayenne—a language with dependent types
Lennart Augustsson · 1998 · 283 citations