Lazy Functional Programming Languages and Persistent Amortized Data Structures

Chris Okasaki
Carnegie Mellon University

In the programming languages community, researchers have long wondered how to analyze the time complexity of programs written in lazy functional programming languages, while in the algorithms community, researchers have been stymied by the apparent incompatibility of amortization and persistence. Although these two problems appear unrelated, they are in fact closely connected. We will discuss an approach to designing and analyzing lazy persistent amortized data structures that simultaneously addresses both of these problems.

Chris Okasaki

School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213
USA
Email: Chris_Okasaki@cs.cmu.edu
Home page: http://foxnet.cs.cmu.edu/people/cokasaki/home.html

Back to the list of talks