Purely functional data structures

By Chris Okasaki. 1998

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

An Introduction to Probabilistic Programming (2018, background): “Efficient implementations of such functionality may be advantageously achieved via pure functional data structures (Okasaki, 1999).”
A Primer on Neural Network Models for Natural Language Processing (2015, background): “Dealing with pop operation is more challenging, but can be solved by using the persistent-stack data-structure (Okasaki, 1999; Goldberg, Zhao, & Huang, 2013).”
O’Mega: An optimizing matrix element generator (2000, background): “The implementation is concise and efficient simultaneously by exploiting the virtues of persistent data structures [6].”
Concepts, Techniques, and Models of Computer Programming (2004, methodology): “For a deeper discussion of this technique including its application to other data structures and a proof of correctness, we recommend [138].”
A history of Haskell: being lazy with class (2007, methodology): “For example, the Edison library of efficient data structures, originated by Okasaki (Okasaki, 1998a) and maintained by Robert Dockins, provides multiple implementations of sequences and collections, organised using type classes.”
Generalised folds for nested datatypes (1999, methodology): “Most of the published work so far (in particular, [ Oka98 ]) uses nested types only as a conceptual tool; the results are translated into programming terms by embedding nested types in regular ones in a systematic way.”
Scrap your boilerplate: a practical design pattern for generic programming (2003, background): “To use this approach directly for practical programming, one needs to write functions to convert to and from between these the above isomorphic types, and the situation becomes noticeably more complicated when there are many mutually-recursive types involved [32, 28], and breaks down altogether when”
Neural Network Methods for Natural Language Processing (2017, unknown): “, 2013, Okasaki, 1999]. Persistent, or immutable, data-structures keep old versions of themselves intact when modified. e persistent stack construction represents a stack as a pointer to the head of a linked list. An empty stack is the empty list. e push operation appends an element to the list, r”
Under Consideration for Publication in Formal Aspects of Computing Disciplined, Efficient, Generalised Folds for Nested Datatypes (unknown): “Random access lists were invented by Okasaki [ Oka98 ] as a means of improving the efficiency of certain operations on traditional lists.”
Nested Datatypes (1998, background): “[3,18,19]) of their usefulness in functional data structure design.”
Consistent and Durable Data Structures for Non-Volatile Byte-Addressable Memory (2011, methodology): “Using PDS-style techniques, we have implemented a proof-of-concept CDDS hash table and, as evidenced by previous work for functional programming languages [35], we are confident that CDDS versioning techniques can be extended to a wide range of data structures.”