<p>To the excellent notes already made, I’ll add <strong>Zippers</strong>.</p>

<p>Huet, Gerard. “Functional Pearl: The Zipper” Journal of Functional Programming 7 (5): 549-554, September 1997.</p>

<p><a href="http://en.wikipedia.org/wiki/Zipper_%28data_structure%29">Wikipedia: Zipper (data structure)</a></p>

CC BY-SA 3.0
2012-08-22T20:29:35.757Z
An example of their use for XML manipulation: http://anti-xml.org/zippers.html
Mechanical snail
CC BY-SA 2.5
2010-12-01T22:52:26.763Z
Zippers are AWESOME. For many use cases, they allow tree based representations to become the "right" choice for many kinds of data where otherwise it'd be a bit more complicated
Carter Tazio Schonwald
CC BY-SA 3.0
2010-09-21T18:06:04.790Z
2013-11-13T03:11:35.530Z
2013-11-13T03:11:35.530Z
Matt Might
<p>Conchon, Filliatre, <a href="http://scholar.google.com/scholar?cluster=8164878778013876774">A Persistent UNION-FIND Data Structure</a> and <a href="http://link.springer.com/chapter/10.1007/978-3-540-78739-6_25">Semi-persistent Data Structures</a>.</p>

CC BY-SA 3.0
2012-06-17T02:36:00.603Z
Radu's link can now be found at https://github.com/septract/jstar-old/blob/9ea84db498acab750b7c7dd5138aab19cd12bdf8/src/utils/persistentarray.ml
jbapple
CC BY-SA 2.5
2010-09-21T08:17:29.367Z
Wow, a persistent UNION-FIND! Thanks!
jkff
CC BY-SA 2.5
2010-09-21T08:18:50.297Z
Well, kind of... See the article.
Radu GRIGore
CC BY-SA 2.5
2010-09-21T08:50:37.877Z
... or, if you prefer, see some code (by Matt Parkinson) http://github.com/septract/jstar/blob/master/src/utils/persistentarray.ml
Radu GRIGore
CC BY-SA 2.5
2010-09-22T11:13:42.297Z
Now I see why the "kind of.." comment had an upvote. They have good performance only when one almost exclusively either does not use persistence, or backtracks all the time: if you often use both "new" and "old" versions, you're screwed. Cool rerooting idea though.
jkff
CC BY-SA 3.0
2010-09-21T08:13:06.220Z
2014-04-26T17:07:46.203Z
2014-04-26T17:07:46.203Z
Radu GRIGore
<p>I'd add McBride's version of zippers as derivatives of data types.</p>

CC BY-SA 3.0
2013-06-16T10:37:02.093Z
Here's [the original paper on derivatives of regular expressions](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.98.4378).
jameshfisher
CC BY-SA 2.5
2010-09-22T22:00:37.243Z
I love that stuff. It's just so cool that the derivative has an application so wildly different from finding rates of change!
SamB
CC BY-SA 2.5
2010-09-22T23:33:06.167Z
SamB, you might also be interested in derivatives of regular expressions (if you didn't already know about them).
jbapple
CC BY-SA 2.5
2010-09-22T02:05:48.960Z
2010-09-22T02:05:48.960Z
none
<p><a href="http://jfla.inria.fr/2010/actes/PDF/bonichon_cuoq.pdf">Rangemaps</a></p>

<p>It is a specialized data structure, but it can be used as a substitute for Martin Erwig's DIET, with slightly different properties, so at least there is one existing data structure to compare it to. The DIET itself was described in an article in JFP in 1998, so perhaps it is not included in Purely Functional Data Structures.</p>

CC BY-SA 2.5
2011-01-28T09:07:31.823Z
2011-01-28T09:07:31.823Z
Complicated see bio
<p>Following up on the 2012 paper linked above, the work on RRB vectors has since been extended and published in ICFP'15.</p>

<p>RRB vector: a practical general purpose immutable sequence
<a href="http://dl.acm.org/citation.cfm?id=2784739" rel="noreferrer">http://dl.acm.org/citation.cfm?id=2784739</a></p>

CC BY-SA 3.0
2016-06-28T16:57:35.073Z
2016-06-28T16:57:35.073Z
Mike Rainey
<h3>New purely functional data structures published since 1998:</h3>

<ul>
<li><p>2001: <strong><a href="http://infoscience.epfl.ch/record/64398" rel="noreferrer">Ideal Hash Trees</a>, and its 2000 predecessor, <a href="http://infoscience.epfl.ch/record/64394" rel="noreferrer">Fast And Space Efficient Trie Searches</a>, by Phil Bagwell</strong>: Apparently used as a fundamental building block in Clojure's standard library.</p></li>
<li><p>2001: <strong><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.1149" rel="noreferrer">A Simple Implementation Technique for Priority Search Queues</a>, by Ralf Hinze</strong>: a really simple and beautiful technique for implementing this important datastructure (useful, say, in the Dijkstra algorithm). The implementation is particularly beautiful and readable due to heavy use of "view patterns".</p></li>
<li><p>2002: <strong><a href="http://www.comlab.ox.ac.uk/people/ralf.hinze/publications/ICFP02.pdf" rel="noreferrer">Bootstrapping one-sided flexible arrays</a>, by Ralf Hinze</strong>: Similar to Okasaki's random-access lists, but they can be tuned to alter the time tradeoff between <code>cons</code> and indexing.</p></li>
<li><p>2003: <strong><a href="http://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/Notes%20on%20Catenable%20Deques.doc" rel="noreferrer">New catenable and non-catenable deques</a>, by Radu Mihaescu and Robert Tarjan</strong>: A new take on some older work (by Kaplan and Tarjan) that Okasaki cites (The <a href="http://www.math.tau.ac.il/~haimk/adv-ds-2000/jacm-final.pdf" rel="noreferrer">most recent version of Kaplan &amp; Tarjan's work was published in 2000</a>). This version is simpler in some ways.</p></li>
<li><p>2005: <strong>Maxiphobic heaps (<a href="http://www.eecs.usma.edu/webs/people/okasaki/sigcse05.pdf" rel="noreferrer">paper</a> and <a href="http://www.eecs.usma.edu/webs/people/okasaki/sigcse05/index.html" rel="noreferrer">code</a>), by Chris Okasaki</strong>: Presented not as a new, more efficient structure, but as a way to teach priority queues.</p></li>
<li><p>2006: <strong><a href="http://www.cs.au.dk/~gerth/pub/esa06trees.html" rel="noreferrer">Purely Functional Worst Case Constant Time Catenable Sorted Lists</a>, by Gerth Stølting Brodal, Christos Makris, and Kostas Tsichlas</strong>: Answers an outstanding question of Kaplan and Tarjan by demonstrating a structure with O(lg n) insert, search, and delete and O(1) concat.</p></li>
<li><p>2008: <strong><a href="http://erikdemaine.org/papers/ConfluentTries_Algorithmica/" rel="noreferrer">Confluently Persistent Tries for Efficient Version Control</a>, by Erik D. Demaine, Stefan Langerman, and Eric Price</strong>: Presents several data structures for tries that have efficient navigation and modification near the leaves. Some are purely functional. Others actually improve a long-standing data structure by Dietz et al. for fully persistent (but not confluently persistent or purely functional) arrays. This paper also presente <strong>purely functional link-cut trees</strong>, sometimes called "dynamic trees".</p></li>
<li><p>2010: <strong><a href="http://matt.might.net/articles/red-black-delete/" rel="noreferrer">A new purely functional delete algorithm for red-black trees</a>, by Matt Might</strong>: Like Okasaki's red-black tree insertion algorithm, this is not a new data structure or a new operation on a data structure, but a new, simpler way to write a known operation.</p></li>
<li><p>2012: <strong><a href="http://infoscience.epfl.ch/record/169879/files/RMTrees.pdf" rel="noreferrer">RRB-Trees: Efficient Immutable Vectors</a>, by Phil Bagwell and Tiark Rompf</strong>: An extension to Hash Array Mapped Tries, supporting immutable vector concatenation, insert-at, and split in O(lg n) time, while maintaining the index, update, and insertion speeds of the original immutable vector.</p></li>
</ul>

<h3>Known in 1997, but not discussed in Okasaki's book:</h3>

<ul>
<li><p><strong>Many other styles of balanced search tree</strong>. AVL, brother, rank-balanced, bounded-balance, and many other balanced search trees can be (and have been) implemented purely functionally by path copying. Perhaps deserving special mention are:</p>

<ul>
<li><strong><a href="http://scholar.google.com/scholar?cluster=10425132226535600788" rel="noreferrer">Biased Search Trees</a>, by Samuel W. Bent, Daniel D. Sleator, and Robert E. Tarjan</strong>: A key element in Brodal et al.'s 2006 paper and Demaine et al.'s 2008 paper.</li>
</ul></li>
<li><p><strong><a href="http://cs.bham.ac.uk/~mhe/papers/exhaustive.pdf" rel="noreferrer">Infinite sets that admit fast exhaustive search</a>, by Martín Escardó</strong>: Perhaps not a data structure <em>per se</em>.</p></li>
<li><p><strong><a href="http://www.eecs.usma.edu/webs/people/okasaki/jfp97.ps" rel="noreferrer">Three algorithms on Braun Trees</a>, by Chris Okasaki</strong>: Braun trees offer many stack operations in worst-case O(lg n). This bound is surpassed by many other data structures, but Braun trees have a <code>cons</code> operation lazy in its second argument, and so can be used as infinite stacks in some ways that other structures cannot.</p></li>
<li><p><strong><a href="http://scholar.google.com/scholar?cluster=2335375395981576930" rel="noreferrer">The relaxed min-max heap: A mergeable double-ended priority queue</a> and <a href="http://scholar.google.com/scholar?cluster=9505131584786452948" rel="noreferrer">The KD heap: An efficient multi-dimensional priority queue</a>, by Yuzheng Ding and Mark Allen Weiss</strong>: These happen to be purely functional, though this is not discussed in the papers. I do not think the time bounds achieved are any better than those that can be achieved by using finger trees (of Hinze &amp; Paterson or Kaplan &amp; Tarjan) as k-dimensional priority queues, but I think the structures of Ding &amp; Weiss uses less space.</p></li>
<li><p><strong><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.185.2421" rel="noreferrer">The Zipper</a>, by Gérard Huet</strong>: Used in many other data structures (such as Hinze &amp; Paterson's finger trees), this is a way of turning a data structure inside-out.</p></li>
<li><p><strong>Difference lists</strong> are O(1) catenable lists with an O(n) transformation to usual <code>cons</code> lists. They have apparently been known since antiquity in the Prolog community, where they have an O(1) transformation to usual <code>cons</code> lists. The O(1) transformation seems to be impossible in traditional functional programming, but Minamide's <a href="http://dl.acm.org/citation.cfm?id=268953" rel="noreferrer">hole abstraction</a>, from POPL '98, discusses a way of allowing O(1) append and O(1) transformation within pure functional programming. Unlike the usual functional programming implementations of difference lists, which are based on function closures, hole abstractions are essentially the same (in both their use and their implementation) as Prolog difference lists. However, it seems that for years the only person that noticed this was <a href="http://requestforlogic.blogspot.com/2011/08/holey-data-postscript-hole-abstraction.html" rel="noreferrer">one of Minamide's reviewers</a>.</p></li>
<li><p><strong>Uniquely represented dictionaries</strong> support insert, update, and lookup with the restriction that no two structures holding the same elements can have distinct shapes. To give an example, sorted singly-linked lists are uniquely represented, but traditional AVL trees are not. Tries are also uniquely represented. <a href="https://www.cs.princeton.edu/research/techreps/TR-267-90" rel="noreferrer">Tarjan and Sundar, in "Unique binary search tree representations and equality-testing of sets and sequences"</a>, showed a purely functional uniquely represented dictionary that supports searches in logarithmic time and updates in $O(\sqrt{n})$ time. However, it uses $\Theta(n \lg n)$ space. There is a <a href="https://github.com/jbapple/unique" rel="noreferrer">simple representation</a> using <a href="http://alexandria.tue.nl/repository/notdare/772185.pdf" rel="noreferrer">Braun trees</a> that uses only linear space but has update time of $\Theta(\sqrt{n \lg n})$ and search time of $\Theta(\lg^2 n)$</p></li>
</ul>

<h3>Mostly functional data structures, before, during, and after Okasaki's book:</h3>

<ul>
<li><p><strong>Many procedures for making data structures persistent, fully persistent, or confluently persistent</strong>: Haim Kaplan wrote <a href="http://www.math.tau.ac.il/~haimk/papers/persistent-survey.ps" rel="noreferrer">an excellent survey on the topic</a>. See also above the work of Demaine et al., who demonstrate a fully persistent array in $O(m)$ space (where $m$ is the number of operations ever performed on the array) and $O(\lg \lg n)$ expected access time.</p></li>
<li><p>1989: <strong><a href="http://acs.lbl.gov/~aragon/treaps.html" rel="noreferrer">Randomized Search Trees</a> by Cecilia R. Aragon and Raimund Seidel</strong>: These were discussed in a purely functional setting by Guy E. Blelloch and Margaret Reid-Miller in <a href="http://www.cs.cmu.edu/afs/cs.cmu.edu/project/scandal/public/papers/treaps-spaa98.html" rel="noreferrer">Fast Set Operations Using Treaps</a>
and by Dan Blandford and Guy Blelloch in <a href="http://www.cs.cmu.edu/afs/cs/project/pscico/pscico/papers/fingertrees/main.pdf" rel="noreferrer">Functional Set Operations with Treaps</a> (<a href="http://www.cs.cmu.edu/afs/cs/project/pscico/pscico/src/fingertrees/" rel="noreferrer">code</a>). They provide all of the operations of purely functional fingertrees and biased search trees, but require a source of randomness, making them not purely functional. This may also invalidate the time complexity of the operations on treaps, assuming an adversary who can time operations and repeat the long ones. (This is the same reason why imperative amortization arguments aren't valid in a persistent setting, but it requires an adversary with a stopwatch)</p></li>
<li><p>1997: <strong><a href="http://www.lsi.upc.edu/~peypoch/investigacio/reports.dir/RAIRO.ps.gz" rel="noreferrer">Skip-trees, an alternative data structure to Skip-lists in a concurrent approach</a>, by Xavier Messeguer and <a href="http://www.cs.clemson.edu/~bcdean/paper11.html" rel="noreferrer">Exploring the Duality Between Skip Lists and Binary Search Trees</a>, by Brian C. Dean and Zachary H. Jones</strong>: Skip lists are not purely functional, but they can be implemented functionally as trees. Like treaps, they require a source of random bits. (It is possible to make skip lists deterministic, but, after translating them to a tree, I think they are just another way of looking at 2-3 trees.)</p></li>
<li><p>1998: <strong>All of the amortized structures in Okasaki's book!</strong> Okasaki invented this new method for mixing amortization and functional data structures, which were previously thought to be incompatible. It depends upon memoization, which, as Kaplan and Tarjan have sometimes mentioned, is actually a side effect. In some cases (<a href="http://rethinkdb.com/jobs/" rel="noreferrer">such as PFDS on SSDs for performance reasons</a>), this may be inappropriate.</p></li>
<li><p>1998: <strong><a href="http://www.math.tau.ac.il/~haimk/adv-ds-2000/okasaki-kaplan-tarjan-sicomp.ps" rel="noreferrer">Simple Confluently Persistent Catenable Lists</a>, by Haim Kaplan, Chris Okasaki, and Robert E. Tarjan</strong>: Uses modification under the hood to give amortized O(1) catenable deques, presenting the same interface as an earlier (purely functional, but with memoization) version appearing in Okasaki's book. Kaplan and Tarjan had earlier created a purely functional O(1) worst-case structure, but it is substantially more complicated.</p></li>
<li><p>2007: As mentioned in another answer on this page, <a href="http://www.lri.fr/~filliatr/ftp/publis/spds-rr.pdf" rel="noreferrer">semi-persistent data structures</a> and <a href="http://www.lri.fr/~filliatr/puf/" rel="noreferrer">persistent union-find</a> by Sylvain Conchon and Jean-Christophe Filliâtre</p></li>
</ul>

<h3>Techniques for verifying functional data structures, before, during, and after Okasaki's book:</h3>

<ul>
<li><p><strong>Phantom types</strong> are an old method for creating an API that does not allow certain ill-formed operations. A sophisticated use of them can be found in Oleg Kiselyov and Chung-chieh Shan's <a href="http://okmij.org/ftp/Computation/lightweight-dependent-typing.html#Lightweight" rel="noreferrer">Lightweight Static Capabilities</a>.</p></li>
<li><p><strong>Nested types</strong> are not actually more recent than 1998 - Okasaki even uses them in his book. There are many other examples that are not in Okasaki's book; some are new, and some are old. They include:</p>

<ul>
<li>Stefan Kahrs's <a href="http://www.cs.kent.ac.uk/pubs/2001/1293/index.html" rel="noreferrer">Red-black trees with types</a> (<a href="http://www.cs.kent.ac.uk/people/staff/smk/redblack/rb.html" rel="noreferrer">code</a>)</li>
<li>Ross Paterson's <a href="http://www.haskell.org/pipermail/haskell/2003-April/011693.html" rel="noreferrer">AVL trees</a> (<a href="http://www.cse.unsw.edu.au/~dons/haskell-1990-2006/msg14064.html" rel="noreferrer">mirror</a>)</li>
<li>Chris Okasaki's <a href="http://www.eecs.usma.edu/webs/people/okasaki/icfp99.ps" rel="noreferrer">From fast exponentiation to square matrices: an adventure in types</a></li>
<li>Richard S. Bird and Ross Peterson's <a href="http://web.comlab.ox.ac.uk/oucl/work/richard.bird/online/BirdPaterson99DeBruijn.pdf" rel="noreferrer">de Bruijn notation as a nested datatype</a></li>
<li>Ralf Hinze's <a href="http://web.comlab.ox.ac.uk/oucl/work/ralf.hinze/publications/IAI-TR-98-12.ps.gz" rel="noreferrer">Numerical Representations as Higher-Order Nested Datatypes</a>.</li>
</ul></li>
<li><p><strong>GADTs</strong> are not all that new, either. They are a recent addition to Haskell and some MLs, but they have been present, I think, in <a href="https://sympa-roc.inria.fr/wws/arc/coq-club/2010-09/msg00072.html" rel="noreferrer">various typed lambda calculi since the 1970s</a>.</p></li>
<li><p>2004-2010: <strong>Coq and Isabelle for correctness</strong>. Several people have used theorem provers to verify the correctness of purely functional data structures. Coq can extract these verifications to working code in Haskell, OCaml, and Scheme; Isabelle can extract to Haskell, ML, and OCaml.</p>

<ul>
<li>Coq:

<ul>
<li>Pierre Letouzey and Jean-Christophe Filliâtre <a href="http://www.lri.fr/~filliatr/fsets/" rel="noreferrer">formalized red-black and AVL(ish) trees, finding a bug in the OCaml standard library in the process</a>.</li>
<li>I <a href="http://code.google.com/p/priority-queues/" rel="noreferrer">formalized Brodal and Okasaki's asymptotically optimal priority queues</a>.</li>
<li>Arthur Charguéraud <a href="http://www.chargueraud.org/softs/cfml/" rel="noreferrer">formalized 825 of the 1,700 lines of ML in Okasaki's book</a>.</li>
</ul></li>
<li>Isabelle:

<ul>
<li>Tobias Nipkow and Cornelia Pusch <a href="http://afp.sourceforge.net/entries/AVL-Trees.shtml" rel="noreferrer">formalized AVL trees</a>.</li>
<li>Viktor Kuncak formalized <a href="http://afp.sourceforge.net/entries/BinarySearchTree.shtml" rel="noreferrer">unbalanced binary search trees</a>.</li>
<li>Peter Lammich published <a href="http://wwwmath.uni-muenster.de:8010/sev/staff/lammich/isabelle/#collections" rel="noreferrer">The Isabelle Collections framework</a>, which includes formalizations of efficient purely functional data structures like red-black trees and tries, as well as data structures that are less efficient when used persistently, such as two-stack-queues (without Okasaki's laziness trick) and hash tables.</li>
<li>Peter Lammich also published formalizations of <a href="http://afp.sourceforge.net/devel-entries/Tree-Automata.shtml" rel="noreferrer">tree automata</a>, <a href="http://afp.sourceforge.net/devel-entries/Finger-Trees.shtml" rel="noreferrer">Hinze &amp; Patterson's finger trees</a> (with Benedikt Nordhoff and Stefan Körner), and <a href="http://afp.sourceforge.net/devel-entries/Binomial-Heaps.shtml" rel="noreferrer">Brodal and Okasaki's purely functional priority queues</a> (with Rene Meis and Finn Nielsen).</li>
<li>René Neumann formalized <a href="http://afp.sourceforge.net/devel-entries/Binomial-Queues.shtml" rel="noreferrer">binomial priority queues</a>.</li>
</ul></li>
</ul></li>
<li><p>2007: <strong><a href="http://www.cs.cmu.edu/~joshuad/papers/stardust/" rel="noreferrer">Refined Typechecking with Stardust</a>, by Joshua Dunfield</strong>: This paper uses refinement types for ML to find errors in SMLNJ's red-black tree delete function.</p></li>
<li><p>2008: <strong><a href="http://www.cs.nott.ac.uk/~nad/publications/danielsson-popl2008.html" rel="noreferrer">Lightweight Semiformal Time Complexity Analysis for Purely Functional Data Structures</a> by Nils Anders Danielsson</strong>: Uses Agda with manual annotation to prove time bounds for some PFDS.</p></li>
</ul>

<h3>Imperative data structures or analyses not discussed in Okasaki's book, but related to purely functional data structures:</h3>

<ul>
<li><p><strong><a href="http://www.cs.princeton.edu/~chazelle/pubs/sheap.pdf" rel="noreferrer">The Soft Heap: An Approximate Priority Queue with Optimal Error Rate</a>, by Bernard Chazelle</strong>: This data structure does not use arrays, and so has tempted <a href="http://tunes.org/~nef//logs/haskell/10.05.11" rel="noreferrer">first the #haskell IRC channel</a> and <a href="https://stackoverflow.com/questions/3402361/purely-functional-soft-heap">later Stack Overflow users</a>, but it includes <code>delete</code> in o(lg n), which is usually not possible in a functional setting, and imperative amortized analysis, which is not valid in a purely functional setting.</p></li>
<li><p><strong>Balanced binary search trees with O(1) finger updates</strong>. In <a href="http://www.cs.cmu.edu/~sleator/papers/Persistence.htm" rel="noreferrer">Making Data Structures Persistent</a>, James R Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan present a method for grouping the nodes in a red-black tree so that persistent updates require only O(1) space. The purely functional deques and finger trees designed by Tarjan, Kaplan, and Mihaescu all use a very similar grouping technique to allow O(1) updates at both ends. <a href="http://scholar.google.com/scholar?cluster=1646762318420773825" rel="noreferrer">AVL-trees for localized search</a> by Athanasios K. Tsakalidis works similarly.</p></li>
<li><p><strong>Faster pairing heaps or better bounds for pairing heaps</strong>: Since Okasaki's book was published, several new analyses of imperative pairing heaps have appeared, including <a href="http://siam.org/proceedings/soda/2009/SODA09_052_elmasrya.pdf" rel="noreferrer">Pairing heaps with O(log log n) decrease Cost</a> by Amr Elmasry and <a href="http://www.eecs.umich.edu/~pettie/papers/focs05.pdf" rel="noreferrer">Towards a Final Analysis of Pairing Heaps</a> by Seth Pettie. It may be possible to apply some of this work to Okasaki's lazy pairing heaps.</p></li>
<li><p><strong>Deterministic biased finger trees</strong>: In <a href="http://www.ics.uci.edu/~goodrich/pubs/bsl.pdf" rel="noreferrer">Biased Skip Lists</a>, by Amitabha Bagchi, Adam L. Buchsbaum, and Michael T. Goodrich, a design is presented for deterministic biased skip lists. Through the skip list/tree transformation mentioned above, it may be possible to make deterministic biased search trees. The finger biased skip lists described by John Iacono and Özgür Özkan in <a href="http://arxiv.org/abs/1002.4248" rel="noreferrer">Mergeable Dictionaries</a> might then be possible on biased skip trees. A biased finger tree is suggested by Demaine et al. in their paper on purely functional tries (see above) as a way to reduce the time-and space bounds on finger update in tries.</p></li>
<li><p><strong><a href="http://doi.acm.org/10.1145/301970.301973" rel="noreferrer">The String B-Tree: A New Data Structure for String Search in External Memory and its Applications</a> by Paolo Ferragina and Roberto Grossi</strong> is a well studied data structure combining the benefits of tries and B-trees.</p></li>
</ul>

CC BY-SA 3.0
2011-09-08T03:52:43.007Z
Why Bagwell's VList isn't considered? there is even a Wikipedia article: https://secure.wikimedia.org/wikipedia/en/wiki/VList
didest
CC BY-SA 3.0
2011-09-08T11:55:45.633Z
@Diego: If you think they should be included, I hope you will post them in an answer. I didn't include them only because I had forgotten about them, but I forgot about them because they aren't very functional -- they degrade to simple cons lists under heavy persistent usage.
jbapple
CC BY-SA 3.0
2012-06-15T19:56:32.103Z
Hmm, is your spelling of the author's name “Radu Mihaescu” right, or is it “Radu Mihaesau” as it appears in the article you linked to?
Zsbán Ambrus
CC BY-SA 3.0
2012-06-17T02:21:40.997Z
After Googling for this name, I think "Radu Mihaescu" is correct.
jbapple
CC BY-SA 3.0
2013-03-04T11:31:33.027Z
Note that Isabelle/HOL can generate code for SML, OCaml, Haskell, Scala.  The Haskabelle tool can also import Haskell into Isabelle/HOL.
Makarius
CC BY-SA 3.0
2013-03-04T11:34:10.250Z
The terminology of "programm extraction" is one of Coq: you take a constructive proof and make an executable program from it, stripping away some things.  In Isabelle this is called "code generation" and works differently, using the HOL *specifications* as pseudo-code, not the proofs.  Proof extraction in Isabelle/HOL according to Berghofer does work like Coq, but is rarely used these days.
Makarius
CC BY-SA 4.0
2018-07-29T12:01:14.043Z
I'd like to propose to potentially add https://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/aplicative.pdf ('APLicative programming with Naperian Functors') to this list.
Qqwy
CC BY-SA 2.5
2010-09-22T19:39:48.863Z
And Brodal/Okasaki's Boostrapped Skew Binomial Heaps, unless I missed it in there.
Edward Kmett
CC BY-SA 2.5
2010-09-22T20:00:04.840Z
Edward Kmett: Boostrapped Skew Binomial Heaps are described in the bootstrapping chapter of Okasaki's book.
jbapple
CC BY-SA 2.5
2010-09-30T10:33:42.647Z
Great list! Which makes me wish Okasaki would publish a second edition.
Radu GRIGore
CC BY-SA 3.0
2010-09-21T16:13:43.547Z
2014-09-27T21:04:10.507Z
2017-05-23T11:33:33.907Z
jbapple
<p>Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few:</p>

<ul>
<li><a href="http://hackage.haskell.org/packages/archive/containers/0.1.0.1/doc/html/Data-IntMap.html">IntMap</a> (also invented by Okasaki in 1998, but not present in that book)</li>
<li><a href="http://apfelmus.nfshost.com/articles/monoid-fingertree.html">Finger trees</a> (and their generalization over monoids)</li>
</ul>

<p>There are also some interesting ways of implementing already known datastructures, such as using "nested types" or "generalized algebraic datatypes" to ensure tree invariants.</p>

<p>Which other new ideas have appeared since 1998 in this area?</p>

CC BY-SA 3.0
2016-01-04T12:33:08.840Z
[Okasaki's blog post from 2008 for the 10th anniversary of the book](http://okasaki.blogspot.ca/2008/02/ten-years-of-purely-functional-data.html)
Kaveh
CC BY-SA 2.5
2010-09-21T08:07:08.737Z
Nice question. I just had a student asking me about this, and didn't know the answer.
Suresh Venkat
CC BY-SA 2.5
2010-09-21T13:01:24.100Z
This is OK for here, but you might get better answers on Stack Overflow.  If you ask there, be sure and link to the discussion here.
Charles Stewart
CC BY-SA 2.5
2010-09-21T22:52:32.253Z
Well the Haskell Reddit has seen this so there will be some good answers coming in from there too but excellent question. Just being halfway through Okasaki's book I was wondering the same think myself. +1
Robert Massaioli
CC BY-SA 2.5
2010-09-22T18:44:41.693Z
[This inspired me to ask a related question](http://cstheory.stackexchange.com/questions/1586/what-are-the-outstanding-questions-in-purely-functional-data-structures).
jbapple
<reference-request><big-list><ds.data-structures><functional-programming>
What's new in purely functional data structures since Okasaki?
jkff
# What's new in purely functional data structures since Okasaki?

(Asked by: username_0 on 2010-09-21)

Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few:

* [IntMap](http://hackage.haskell.org/packages/archive/containers/0.1.0.1/doc/html/Data-IntMap.html) (also invented by Okasaki in 1998, but not present in that book)
* [Finger trees](http://apfelmus.nfshost.com/articles/monoid-fingertree.html) (and their generalization over monoids)

There are also some interesting ways of implementing already known datastructures, such as using "nested types" or "generalized algebraic datatypes" to ensure tree invariants.

Which other new ideas have appeared since 1998 in this area?

**Tags:** reference-request, big-list, ds.data-structures, functional-programming
> **Comments:**
> **username_2**: Nice question. I just had a student asking me about this, and didn't know the answer.  
> **username_3**: This is OK for here, but you might get better answers on Stack Overflow.  If you ask there, be sure and link to the discussion here.  
> **username_4**: Well the Haskell Reddit has seen this so there will be some good answers coming in from there too but excellent question. Just being halfway through Okasaki's book I was wondering the same think myself. +1  
> **username_5**: [This inspired me to ask a related question](http://cstheory.stackexchange.com/questions/1586/what-are-the-outstanding-questions-in-purely-functional-data-structures).  
> **username_1**: [Okasaki's blog post from 2008 for the 10th anniversary of the book](http://okasaki.blogspot.ca/2008/02/ten-years-of-purely-functional-data.html)  

---

## 6 answers

### Answer by username_5 on 2010-09-21. Score: 608 | Accepted answer

### New purely functional data structures published since 1998:

* 2001: **[Ideal Hash Trees](http://infoscience.epfl.ch/record/64398), and its 2000 predecessor, [Fast And Space Efficient Trie Searches](http://infoscience.epfl.ch/record/64394), by Phil Bagwell**: Apparently used as a fundamental building block in Clojure's standard library.
* 2001: **[A Simple Implementation Technique for Priority Search Queues](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.1149), by Ralf Hinze**: a really simple and beautiful technique for implementing this important datastructure (useful, say, in the Dijkstra algorithm). The implementation is particularly beautiful and readable due to heavy use of "view patterns".
* 2002: **[Bootstrapping one-sided flexible arrays](http://www.comlab.ox.ac.uk/people/ralf.hinze/publications/ICFP02.pdf), by Ralf Hinze**: Similar to Okasaki's random-access lists, but they can be tuned to alter the time tradeoff between `cons` and indexing.
* 2003: **[New catenable and non-catenable deques](http://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/Notes%20on%20Catenable%20Deques.doc), by Radu Mihaescu and Robert Tarjan**: A new take on some older work (by Kaplan and Tarjan) that Okasaki cites (The [most recent version of Kaplan & Tarjan's work was published in 2000](http://www.math.tau.ac.il/~haimk/adv-ds-2000/jacm-final.pdf)). This version is simpler in some ways.
* 2005: **Maxiphobic heaps ([paper](http://www.eecs.usma.edu/webs/people/okasaki/sigcse05.pdf) and [code](http://www.eecs.usma.edu/webs/people/okasaki/sigcse05/index.html)), by Chris Okasaki**: Presented not as a new, more efficient structure, but as a way to teach priority queues.
* 2006: **[Purely Functional Worst Case Constant Time Catenable Sorted Lists](http://www.cs.au.dk/~gerth/pub/esa06trees.html), by Gerth Stølting Brodal, Christos Makris, and Kostas Tsichlas**: Answers an outstanding question of Kaplan and Tarjan by demonstrating a structure with O(lg n) insert, search, and delete and O(1) concat.
* 2008: **[Confluently Persistent Tries for Efficient Version Control](http://erikdemaine.org/papers/ConfluentTries_Algorithmica/), by Erik D. Demaine, Stefan Langerman, and Eric Price**: Presents several data structures for tries that have efficient navigation and modification near the leaves. Some are purely functional. Others actually improve a long-standing data structure by Dietz et al. for fully persistent (but not confluently persistent or purely functional) arrays. This paper also presente **purely functional link-cut trees**, sometimes called "dynamic trees".
* 2010: **[A new purely functional delete algorithm for red-black trees](http://matt.might.net/articles/red-black-delete/), by Matt Might**: Like Okasaki's red-black tree insertion algorithm, this is not a new data structure or a new operation on a data structure, but a new, simpler way to write a known operation.
* 2012: **[RRB-Trees: Efficient Immutable Vectors](http://infoscience.epfl.ch/record/169879/files/RMTrees.pdf), by Phil Bagwell and Tiark Rompf**: An extension to Hash Array Mapped Tries, supporting immutable vector concatenation, insert-at, and split in O(lg n) time, while maintaining the index, update, and insertion speeds of the original immutable vector.

### Known in 1997, but not discussed in Okasaki's book:

* **Many other styles of balanced search tree**. AVL, brother, rank-balanced, bounded-balance, and many other balanced search trees can be (and have been) implemented purely functionally by path copying. Perhaps deserving special mention are:

  + **[Biased Search Trees](http://scholar.google.com/scholar?cluster=10425132226535600788), by Samuel W. Bent, Daniel D. Sleator, and Robert E. Tarjan**: A key element in Brodal et al.'s 2006 paper and Demaine et al.'s 2008 paper.
* **[Infinite sets that admit fast exhaustive search](http://cs.bham.ac.uk/~mhe/papers/exhaustive.pdf), by Martín Escardó**: Perhaps not a data structure *per se*.
* **[Three algorithms on Braun Trees](http://www.eecs.usma.edu/webs/people/okasaki/jfp97.ps), by Chris Okasaki**: Braun trees offer many stack operations in worst-case O(lg n). This bound is surpassed by many other data structures, but Braun trees have a `cons` operation lazy in its second argument, and so can be used as infinite stacks in some ways that other structures cannot.
* **[The relaxed min-max heap: A mergeable double-ended priority queue](http://scholar.google.com/scholar?cluster=2335375395981576930) and [The KD heap: An efficient multi-dimensional priority queue](http://scholar.google.com/scholar?cluster=9505131584786452948), by Yuzheng Ding and Mark Allen Weiss**: These happen to be purely functional, though this is not discussed in the papers. I do not think the time bounds achieved are any better than those that can be achieved by using finger trees (of Hinze & Paterson or Kaplan & Tarjan) as k-dimensional priority queues, but I think the structures of Ding & Weiss uses less space.
* **[The Zipper](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.185.2421), by Gérard Huet**: Used in many other data structures (such as Hinze & Paterson's finger trees), this is a way of turning a data structure inside-out.
* **Difference lists** are O(1) catenable lists with an O(n) transformation to usual `cons` lists. They have apparently been known since antiquity in the Prolog community, where they have an O(1) transformation to usual `cons` lists. The O(1) transformation seems to be impossible in traditional functional programming, but Minamide's [hole abstraction](http://dl.acm.org/citation.cfm?id=268953), from POPL '98, discusses a way of allowing O(1) append and O(1) transformation within pure functional programming. Unlike the usual functional programming implementations of difference lists, which are based on function closures, hole abstractions are essentially the same (in both their use and their implementation) as Prolog difference lists. However, it seems that for years the only person that noticed this was [one of Minamide's reviewers](http://requestforlogic.blogspot.com/2011/08/holey-data-postscript-hole-abstraction.html).
* **Uniquely represented dictionaries** support insert, update, and lookup with the restriction that no two structures holding the same elements can have distinct shapes. To give an example, sorted singly-linked lists are uniquely represented, but traditional AVL trees are not. Tries are also uniquely represented. [Tarjan and Sundar, in "Unique binary search tree representations and equality-testing of sets and sequences"](https://www.cs.princeton.edu/research/techreps/TR-267-90), showed a purely functional uniquely represented dictionary that supports searches in logarithmic time and updates in $O(\sqrt{n})$ time. However, it uses $\Theta(n \lg n)$ space. There is a [simple representation](https://github.com/jbapple/unique) using [Braun trees](http://alexandria.tue.nl/repository/notdare/772185.pdf) that uses only linear space but has update time of $\Theta(\sqrt{n \lg n})$ and search time of $\Theta(\lg^2 n)$

### Mostly functional data structures, before, during, and after Okasaki's book:

* **Many procedures for making data structures persistent, fully persistent, or confluently persistent**: Haim Kaplan wrote [an excellent survey on the topic](http://www.math.tau.ac.il/~haimk/papers/persistent-survey.ps). See also above the work of Demaine et al., who demonstrate a fully persistent array in $O(m)$ space (where $m$ is the number of operations ever performed on the array) and $O(\lg \lg n)$ expected access time.
* 1989: **[Randomized Search Trees](http://acs.lbl.gov/~aragon/treaps.html) by Cecilia R. Aragon and Raimund Seidel**: These were discussed in a purely functional setting by Guy E. Blelloch and Margaret Reid-Miller in [Fast Set Operations Using Treaps](http://www.cs.cmu.edu/afs/cs.cmu.edu/project/scandal/public/papers/treaps-spaa98.html)
  and by Dan Blandford and Guy Blelloch in [Functional Set Operations with Treaps](http://www.cs.cmu.edu/afs/cs/project/pscico/pscico/papers/fingertrees/main.pdf) ([code](http://www.cs.cmu.edu/afs/cs/project/pscico/pscico/src/fingertrees/)). They provide all of the operations of purely functional fingertrees and biased search trees, but require a source of randomness, making them not purely functional. This may also invalidate the time complexity of the operations on treaps, assuming an adversary who can time operations and repeat the long ones. (This is the same reason why imperative amortization arguments aren't valid in a persistent setting, but it requires an adversary with a stopwatch)
* 1997: **[Skip-trees, an alternative data structure to Skip-lists in a concurrent approach](http://www.lsi.upc.edu/~peypoch/investigacio/reports.dir/RAIRO.ps.gz), by Xavier Messeguer and [Exploring the Duality Between Skip Lists and Binary Search Trees](http://www.cs.clemson.edu/~bcdean/paper11.html), by Brian C. Dean and Zachary H. Jones**: Skip lists are not purely functional, but they can be implemented functionally as trees. Like treaps, they require a source of random bits. (It is possible to make skip lists deterministic, but, after translating them to a tree, I think they are just another way of looking at 2-3 trees.)
* 1998: **All of the amortized structures in Okasaki's book!** Okasaki invented this new method for mixing amortization and functional data structures, which were previously thought to be incompatible. It depends upon memoization, which, as Kaplan and Tarjan have sometimes mentioned, is actually a side effect. In some cases ([such as PFDS on SSDs for performance reasons](http://rethinkdb.com/jobs/)), this may be inappropriate.
* 1998: **[Simple Confluently Persistent Catenable Lists](http://www.math.tau.ac.il/~haimk/adv-ds-2000/okasaki-kaplan-tarjan-sicomp.ps), by Haim Kaplan, Chris Okasaki, and Robert E. Tarjan**: Uses modification under the hood to give amortized O(1) catenable deques, presenting the same interface as an earlier (purely functional, but with memoization) version appearing in Okasaki's book. Kaplan and Tarjan had earlier created a purely functional O(1) worst-case structure, but it is substantially more complicated.
* 2007: As mentioned in another answer on this page, [semi-persistent data structures](http://www.lri.fr/~filliatr/ftp/publis/spds-rr.pdf) and [persistent union-find](http://www.lri.fr/~filliatr/puf/) by Sylvain Conchon and Jean-Christophe Filliâtre

### Techniques for verifying functional data structures, before, during, and after Okasaki's book:

* **Phantom types** are an old method for creating an API that does not allow certain ill-formed operations. A sophisticated use of them can be found in Oleg Kiselyov and Chung-chieh Shan's [Lightweight Static Capabilities](http://okmij.org/ftp/Computation/lightweight-dependent-typing.html#Lightweight).
* **Nested types** are not actually more recent than 1998 - Okasaki even uses them in his book. There are many other examples that are not in Okasaki's book; some are new, and some are old. They include:

  + Stefan Kahrs's [Red-black trees with types](http://www.cs.kent.ac.uk/pubs/2001/1293/index.html) ([code](http://www.cs.kent.ac.uk/people/staff/smk/redblack/rb.html))
  + Ross Paterson's [AVL trees](http://www.haskell.org/pipermail/haskell/2003-April/011693.html) ([mirror](http://www.cse.unsw.edu.au/~dons/haskell-1990-2006/msg14064.html))
  + Chris Okasaki's [From fast exponentiation to square matrices: an adventure in types](http://www.eecs.usma.edu/webs/people/okasaki/icfp99.ps)
  + Richard S. Bird and Ross Peterson's [de Bruijn notation as a nested datatype](http://web.comlab.ox.ac.uk/oucl/work/richard.bird/online/BirdPaterson99DeBruijn.pdf)
  + Ralf Hinze's [Numerical Representations as Higher-Order Nested Datatypes](http://web.comlab.ox.ac.uk/oucl/work/ralf.hinze/publications/IAI-TR-98-12.ps.gz).
* **GADTs** are not all that new, either. They are a recent addition to Haskell and some MLs, but they have been present, I think, in [various typed lambda calculi since the 1970s](https://sympa-roc.inria.fr/wws/arc/coq-club/2010-09/msg00072.html).
* 2004-2010: **Coq and Isabelle for correctness**. Several people have used theorem provers to verify the correctness of purely functional data structures. Coq can extract these verifications to working code in Haskell, OCaml, and Scheme; Isabelle can extract to Haskell, ML, and OCaml.

  + Coq:
    - Pierre Letouzey and Jean-Christophe Filliâtre [formalized red-black and AVL(ish) trees, finding a bug in the OCaml standard library in the process](http://www.lri.fr/~filliatr/fsets/).
    - I [formalized Brodal and Okasaki's asymptotically optimal priority queues](http://code.google.com/p/priority-queues/).
    - Arthur Charguéraud [formalized 825 of the 1,700 lines of ML in Okasaki's book](http://www.chargueraud.org/softs/cfml/).
  + Isabelle:
    - Tobias Nipkow and Cornelia Pusch [formalized AVL trees](http://afp.sourceforge.net/entries/AVL-Trees.shtml).
    - Viktor Kuncak formalized [unbalanced binary search trees](http://afp.sourceforge.net/entries/BinarySearchTree.shtml).
    - Peter Lammich published [The Isabelle Collections framework](http://wwwmath.uni-muenster.de:8010/sev/staff/lammich/isabelle/#collections), which includes formalizations of efficient purely functional data structures like red-black trees and tries, as well as data structures that are less efficient when used persistently, such as two-stack-queues (without Okasaki's laziness trick) and hash tables.
    - Peter Lammich also published formalizations of [tree automata](http://afp.sourceforge.net/devel-entries/Tree-Automata.shtml), [Hinze & Patterson's finger trees](http://afp.sourceforge.net/devel-entries/Finger-Trees.shtml) (with Benedikt Nordhoff and Stefan Körner), and [Brodal and Okasaki's purely functional priority queues](http://afp.sourceforge.net/devel-entries/Binomial-Heaps.shtml) (with Rene Meis and Finn Nielsen).
    - René Neumann formalized [binomial priority queues](http://afp.sourceforge.net/devel-entries/Binomial-Queues.shtml).
* 2007: **[Refined Typechecking with Stardust](http://www.cs.cmu.edu/~joshuad/papers/stardust/), by Joshua Dunfield**: This paper uses refinement types for ML to find errors in SMLNJ's red-black tree delete function.
* 2008: **[Lightweight Semiformal Time Complexity Analysis for Purely Functional Data Structures](http://www.cs.nott.ac.uk/~nad/publications/danielsson-popl2008.html) by Nils Anders Danielsson**: Uses Agda with manual annotation to prove time bounds for some PFDS.

### Imperative data structures or analyses not discussed in Okasaki's book, but related to purely functional data structures:

* **[The Soft Heap: An Approximate Priority Queue with Optimal Error Rate](http://www.cs.princeton.edu/~chazelle/pubs/sheap.pdf), by Bernard Chazelle**: This data structure does not use arrays, and so has tempted [first the #haskell IRC channel](http://tunes.org/~nef//logs/haskell/10.05.11) and [later Stack Overflow users](https://stackoverflow.com/questions/3402361/purely-functional-soft-heap), but it includes `delete` in o(lg n), which is usually not possible in a functional setting, and imperative amortized analysis, which is not valid in a purely functional setting.
* **Balanced binary search trees with O(1) finger updates**. In [Making Data Structures Persistent](http://www.cs.cmu.edu/~sleator/papers/Persistence.htm), James R Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan present a method for grouping the nodes in a red-black tree so that persistent updates require only O(1) space. The purely functional deques and finger trees designed by Tarjan, Kaplan, and Mihaescu all use a very similar grouping technique to allow O(1) updates at both ends. [AVL-trees for localized search](http://scholar.google.com/scholar?cluster=1646762318420773825) by Athanasios K. Tsakalidis works similarly.
* **Faster pairing heaps or better bounds for pairing heaps**: Since Okasaki's book was published, several new analyses of imperative pairing heaps have appeared, including [Pairing heaps with O(log log n) decrease Cost](http://siam.org/proceedings/soda/2009/SODA09_052_elmasrya.pdf) by Amr Elmasry and [Towards a Final Analysis of Pairing Heaps](http://www.eecs.umich.edu/~pettie/papers/focs05.pdf) by Seth Pettie. It may be possible to apply some of this work to Okasaki's lazy pairing heaps.
* **Deterministic biased finger trees**: In [Biased Skip Lists](http://www.ics.uci.edu/~goodrich/pubs/bsl.pdf), by Amitabha Bagchi, Adam L. Buchsbaum, and Michael T. Goodrich, a design is presented for deterministic biased skip lists. Through the skip list/tree transformation mentioned above, it may be possible to make deterministic biased search trees. The finger biased skip lists described by John Iacono and Özgür Özkan in [Mergeable Dictionaries](http://arxiv.org/abs/1002.4248) might then be possible on biased skip trees. A biased finger tree is suggested by Demaine et al. in their paper on purely functional tries (see above) as a way to reduce the time-and space bounds on finger update in tries.
* **[The String B-Tree: A New Data Structure for String Search in External Memory and its Applications](http://doi.acm.org/10.1145/301970.301973) by Paolo Ferragina and Roberto Grossi** is a well studied data structure combining the benefits of tries and B-trees.

> **Comments:**
> **username_19**: And Brodal/Okasaki's Boostrapped Skew Binomial Heaps, unless I missed it in there.  
> **username_5**: Edward Kmett: Boostrapped Skew Binomial Heaps are described in the bootstrapping chapter of Okasaki's book.  
> **username_9**: Great list! Which makes me wish Okasaki would publish a second edition.  
> **username_15**: Why Bagwell's VList isn't considered? there is even a Wikipedia article: https://secure.wikimedia.org/wikipedia/en/wiki/VList  
> **username_5**: @Diego: If you think they should be included, I hope you will post them in an answer. I didn't include them only because I had forgotten about them, but I forgot about them because they aren't very functional -- they degrade to simple cons lists under heavy persistent usage.  
> **username_16**: Hmm, is your spelling of the author's name “Radu Mihaescu” right, or is it “Radu Mihaesau” as it appears in the article you linked to?  
> **username_5**: After Googling for this name, I think "Radu Mihaescu" is correct.  
> **username_17**: Note that Isabelle/HOL can generate code for SML, OCaml, Haskell, Scala.  The Haskabelle tool can also import Haskell into Isabelle/HOL.  
> **username_17**: The terminology of "programm extraction" is one of Coq: you take a constructive proof and make an executable program from it, stripping away some things.  In Isabelle this is called "code generation" and works differently, using the HOL *specifications* as pseudo-code, not the proofs.  Proof extraction in Isabelle/HOL according to Berghofer does work like Coq, but is rarely used these days.  
> **username_18**: I'd like to propose to potentially add https://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/aplicative.pdf ('APLicative programming with Naperian Functors') to this list.  

---

### Answer by username_6 on 2010-09-21. Score: 69

To the excellent notes already made, I’ll add **Zippers**.

Huet, Gerard. “Functional Pearl: The Zipper” Journal of Functional Programming 7 (5): 549-554, September 1997.

[Wikipedia: Zipper (data structure)](http://en.wikipedia.org/wiki/Zipper_%28data_structure%29)

> **Comments:**
> **username_8**: Zippers are AWESOME. For many use cases, they allow tree based representations to become the "right" choice for many kinds of data where otherwise it'd be a bit more complicated  
> **username_7**: An example of their use for XML manipulation: http://anti-xml.org/zippers.html  

---

### Answer by username_9 on 2010-09-21. Score: 44

Conchon, Filliatre, [A Persistent UNION-FIND Data Structure](http://scholar.google.com/scholar?cluster=8164878778013876774) and [Semi-persistent Data Structures](http://link.springer.com/chapter/10.1007/978-3-540-78739-6_25).

> **Comments:**
> **username_0**: Wow, a persistent UNION-FIND! Thanks!  
> **username_9**: Well, kind of... See the article.  
> **username_9**: ... or, if you prefer, see some code (by Matt Parkinson) http://github.com/septract/jstar/blob/master/src/utils/persistentarray.ml  
> **username_0**: Now I see why the "kind of.." comment had an upvote. They have good performance only when one almost exclusively either does not use persistence, or backtracks all the time: if you often use both "new" and "old" versions, you're screwed. Cool rerooting idea though.  
> **username_5**: Radu's link can now be found at https://github.com/septract/jstar-old/blob/9ea84db498acab750b7c7dd5138aab19cd12bdf8/src/utils/persistentarray.ml  

---

### Answer by username_10 on 2010-09-22. Score: 22

I'd add McBride's version of zippers as derivatives of data types.

> **Comments:**
> **username_12**: I love that stuff. It's just so cool that the derivative has an application so wildly different from finding rates of change!  
> **username_5**: SamB, you might also be interested in derivatives of regular expressions (if you didn't already know about them).  
> **username_11**: Here's [the original paper on derivatives of regular expressions](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.98.4378).  

---

### Answer by username_13 on 2011-01-28. Score: 15

[Rangemaps](http://jfla.inria.fr/2010/actes/PDF/bonichon_cuoq.pdf)

It is a specialized data structure, but it can be used as a substitute for Martin Erwig's DIET, with slightly different properties, so at least there is one existing data structure to compare it to. The DIET itself was described in an article in JFP in 1998, so perhaps it is not included in Purely Functional Data Structures.


---

### Answer by username_14 on 2016-06-28. Score: 9

Following up on the 2012 paper linked above, the work on RRB vectors has since been extended and published in ICFP'15.

RRB vector: a practical general purpose immutable sequence
<http://dl.acm.org/citation.cfm?id=2784739>


---

