Efficient Functional Data Structures

[Matthias Lang]

Eric Newhuis writes:
 > Is there any good information out there on efficient functional data
 > structures?  

The classic is

    Chris Okasaki
    Purely Functional Data Structures
    Cambridge University Press; ISBN: 0521663504; 0 edition (July 1, 1999) 

He also has a lot of articles online at

    http://www.eecs.usma.edu/Personnel/okasaki/pubs.html#cup98

Reading the book was a bit of an "a-ha" experience for me. It
clarified the muddy ideas I had about functional data
structures. Unfortunately half the book is about lazy data structures.

 > I have two concerns.
 > 
 > The small concern:  Every time I add a child node I need to rebuild the
 > trie all the way back up to the root.  {orddict:store (Elem, store
 > (...), ...), ...}

This is a fundamental property of purely functional trees. You can
only get around it by introducing destructive update in one guise or
another. See also:

    http://www.research.avayalabs.com/user/wadler/topics/monads.html

 > Questions for the experts:  What can I do with "textbook" Erlang?  What
 > can I do to cheat (possibly with a C "hack")?  Am I doing things as good
 > as I can with clean Erlang?  What can I do to speed things up?

I haven't tried very hard to understanding your code, so I won't comment.

My experience is that ETS is hard to beat as soon as you get even a
moderate amount of data (a few thousand nodes). Chances for beating
ETS improve if your data structure doesn't have a simple mapping to
ETS or if the data structure tends to be short-lived. Previous 
related discussions:

   http://www.erlang.org/ml-archive/erlang-questions/200010/msg00193.html
   http://www.erlang.org/ml-archive/erlang-questions/200012/msg00045.html

Matthias