---
created_at: '2014-01-18T15:39:36.000Z'
title: What's new in purely functional data structures since Okasaki? (2010)
url: http://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki
author: profquail
points: 67
story_text: ''
comment_text: 
num_comments: 18
story_id: 
story_title: 
story_url: 
parent_id: 
created_at_i: 1390059576
_tags:
- story
- author_profquail
- story_7081191
objectID: '7081191'

---
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?
