---
created_at: '2013-05-13T21:03:26.000Z'
title: Ten Years of Purely Functional Data Structures (2008)
url: http://okasaki.blogspot.ru/2008/02/ten-years-of-purely-functional-data.html
author: ColinWright
points: 165
story_text: ''
comment_text: 
num_comments: 26
story_id: 
story_title: 
story_url: 
parent_id: 
created_at_i: 1368479006
_tags:
- story
- author_ColinWright
- story_5701396
objectID: '5701396'

---
[Source](http://okasaki.blogspot.ru/2008/02/ten-years-of-purely-functional-data.html "Permalink to Teaching, Playing, and Programming: Ten Years of Purely Functional Data Structures")

# Teaching, Playing, and Programming: Ten Years of Purely Functional Data Structures

[skip to main ][1] | [skip to sidebar][2]

#  [ Teaching, Playing, and Programming ][3]

## Friday, February 8, 2008

###  Ten Years of Purely Functional Data Structures 

In 1998, I published a book called **Purely Functional Data Structures**. Ten years later, the book is still selling well. (Every time I get a royalty check, my wife the skeptic says “People are _still_ buying that?!”) The ten-year anniversary seems like a good time to reflect back on my experience with this book.

### Origins

My first introduction to functional programming was at Carnegie Mellon University, where I worked for [Peter Lee][4] and Phil Koopman on an implementation of a subset of [Haskell][5] (called “[Eddie][6]”), written in [Standard ML][7]. So right from the very beginning, I was working with a mix of strict and lazy evaluation.

I've always been fascinated by data structures, and I soon realized that something was strange about data structures in these two languages. On the one hand, when they worked, data structures were more pleasant to work with than in any other languages I had ever used before. On the other hand, sometimes they just didn't work.

The issue was _immutability_. In pure functional programming, all data structures are immutable, meaning that they cannot be changed once created. Of course, data structures frequently need to be changed, so what happens is that you create a new copy of the data structure that incorporates the change, without actually modifying the old copy. This can often be done efficiently by having the new structure share large chunks of the old one. For example, stacks are trivial to implement this way. Tree-like structures such as binary search trees and many kinds of priority queues are almost as easy.

However, some common data structures, such as FIFO queues and arrays, can actually be quite difficult to implement this way. Some people take this as a sign that functional languages are impractical. However, it's not the fault of functional programming per se, but rather of immutability. Immutable data structures are just as awkward to implement in conventional languages such as Java. (Of course, immutable data structures also offer huge advantages, which is why, for example, strings are immutable in Java.)

In 1993, I ran across an [interesting paper][8] by Tyng-Ruey Chuang and Benjamin Goldberg, showing how to implement efficient purely functional queues and double-ended queues. Their result was quite nice, but rather complicated, so I started looking for a simpler approach. Eventually, I came up a much simpler approach based on lazy evaluation, leading to my [first paper][9] in this area. (When I say simpler here, I mean simpler to implement—the new structure was actually harder to analyze than Chuang and Goldberg's.)

Almost immediately after my paper on queues, I worked on a paper about [functional arrays][10], here called _random-access lists_ because they combined the extensibility of lists with the random access of arrays. (Because the lead time on journal papers is longer than the lead time for conferences, this paper actually appeared before the paper on queues, even though it was written later.) The approach I used, which turned out to be very similar to one used earlier by Gene Myers, was based on properties of an obscure number system called _skew binary numbers_. This marked the beginning of a second theme of my work, that of designing implementations of data structures in analogy to number systems. For example, inserting an element into a data structure is similar to incrementing a number, and merging two data structures is similar to adding two numbers. I called this approach _numerical representations_. The idea was to choose or create a number system with the properties you want (such as constant-time addition), and then build the data structure on top of that. The advantage of this approach is that you can often do the hard work in a simplified setting, where you don't have to worry about carrying around the actual data in your data structure.

Amusingly, this paper marked the second round of a circle dance between Rob Hoogerwoord, Tyng-Ruey Chuang, and me. First, Hoogerwoord published a paper on functional queues, then Chuang, then me. And again with functional arrays, first Hoogerwoord published a paper, then Chuang, then me.

Around this time, I was looking for a thesis topic (that period that John Reynolds describes as “making even the best student look bad”). Fortunately, my advisor Peter Lee had patience with me during this search. I considered a bunch of topics related to functional programming, but none of them seemed right. I was enjoying the work I was doing with functional data structures, but there didn't really seem to be enough meat there for a dissertation. That changed one day during a walk in the snow.

I had become fascinated by the idea of concatenation (appending two lists). This is trivial to do in conventional languages using, say, doubly-linked lists. But it's much harder to do efficiently with immutable lists. I thought that I had come up with a new approach, so I made an appointment to talk to Danny Sleator about it. He had been involved in some of the early work in this topic (along with Neil Sarnak and Bob Tarjan), and his office was just a few floors below mine. The day before the meeting, I realized that my approach was completely broken. Afraid of looking like an idiot, I went into a frenzy, playing with different variations, and a few hours later I came up with an approach again based on lazy evaluation. I was sure that this approach worked, but I had no idea how to prove it. (Again, this was a case where the implementation was simple, but the analysis was a bear.) My wife had our car somewhere else that day, so I ended up walking home. The walk usually took about 45 minutes, but it was snowing pretty hard, so it took about twice that long. The whole way home I thought about nothing but how to analyze my data structure. I knew it had something to do with amortization, but the usual techniques of amortization weren't working. About halfway home, I came up with the idea of using _debits_ instead of credits, and by the time I got home the entire framework of how to analyze data structures involving lazy evaluation had crystallized in my head.

With this framework in mind, I now believed that there was enough meat there for a dissertation, and I sailed through my thesis proposal and, about a year later, my thesis defense.

### The Book

After my defense, Peter Lee suggested that I try to publish my dissertation as a book. He contacted two publishers he had worked with before, and one of them, Lauren Cowles of Cambridge University Press, bit.

The process of turning my dissertation into a book was pure joy. I thought that the basic organization of my dissertation was pretty solid, so mostly I was able to focus on adding and adjusting things to make it work better as a book. For example, I no longer had the constraint from my dissertation of having to focus on original work, so I was free to add data structures that had been developed by other people.

The main additions were expanded introductory material (such as my simplification of red-black trees, which was developed a few weeks after my thesis defense in a series of emails with Richard Bird), exercises, and an appendix including all the source code in Haskell (the main text used source code in Standard ML).

After several months of hacking, I was able to ship off a giant Postscript file to Lauren Cowles, and that was that.

Well, not quite. Lauren asked me what I wanted for cover art. My wife was an avid quilter, and I liked the idea of having a suitably geeky quilt pattern on the cover. I adapted a quilt pattern called _Flying Geese_, and sent a sketch to Lauren, who got a graphic artist to draw up the final version. I was quite happy with it. Later, I found out that Flying geese was actually the name of a different pattern, and to this day, I don't know the correct name of the pattern. It looks a little different on the book than in quilts because quilters usually only use two levels of the recursion, but I used three.

### Reactions

Initial reviews were positive and the hardcover edition sold out pretty quickly, so Cambridge University Press released a paperback edition the following year. I don't know of any courses that used it as the main textbook (it would have to be a pretty specialized course to do that), but several mainstream courses used it as a supplementary textbook.

Sales were steady but trending downward, until 2004, when a book review by Andrew Cooke appeared on [Slashdot][11]. After that, sales doubled and have stayed at that level for several years. Of course, I can't be sure this increase was because of Slashdot, but it seems likely. Thanks, Andrew!

The most interesting place the book has shown up was in the data of a [TopCoder][12] programming contest problem involving sorting books on a bookshelf. It was part of a list of CS textbooks. (And, no, I wasn't the author of the problem, although I have written some problems for TopCoder.)

The funniest moment about the book was when I worked at Columbia University. A potential grad student from an unrelated field in CS was visiting from Germany, and I was talking to him about the department. When I told him about my research, he said, “My roommate has been reading a book about something like that. I don't remember the name, but do you know which book I mean?” I reached over and pulled my book off the shelf and said, “Do you mean this one?” His mouth fell open.

The most flattering review of the book appeared a few years ago in a [blog][13] by José Antonio Ortega Ruiz, who said

> “The exposition is extremely elegant and synthetic, and i’ve spent many, many hours immersed in its 220 pages (i can’t think of any other programming book with a better signal to noise ratio, really).”

Thanks, jao!

### Complaints

Of course, you can't please everybody. The most common complaints I've heard are

* **No hash tables.** This was mentioned in the first review of the book on [Amazon][14], which called the lack of hash tables a “major omission, likely because they don't fit well into a functional environment.” More than a year later, a second reviewer mentioned that hash tables are in fact in the book, but buried in an exercise. Both reviewers are correct. I only gave a very short description of hash tables in an exercise, because there just wasn't that much to say. A hash table is basically the composition of two finite maps, one approximate and one exact. The choice of what structures to use for those finite maps are up to you. Typically, an array is used for the approximate map, but, as the first reviewer noted, arrays do not fit well into a functional environment.
* **No delete for red-black trees.** I present my simplified form of red-black trees very early in the book as an introduction to functional data structures, but I only describe insertions, not deletions. There were two main reasons for that omission. First, deletions are much messier than insertions, and the introduction did not seem like the right place for a lot of messy details. Second, and more importantly, probably 95+% of uses of functional red-black trees don't need deletions anyway. Because the trees are immutable, when you want to delete something, you can simply revert back to a previous version of the tree from before the unwanted item was inserted. This is almost always both the easiest and the right thing to do. The exception is when you inserted something else that you want to keep after the item to be deleted, but this is extremely rare.
* **Why Standard ML?** In the last 10 years, Haskell has become steadily more popular, while Standard ML has largely been replaced by OCaml. A frequent complaint has been people wishing that Haskell was in the main text, with Standard ML (or OCaml) in the appendix, instead of the reverse. Even at the time, I debated with myself about the choice of Standard ML, particularly because in some chapters I had to fake extensions to the language, such as lazy evaluation and polymorphic recursion. I went with Standard ML for two main reasons. First, I wanted to be able to distinguish between lazy evaluation and strict evaluation, which was much more difficult in Haskell. Second, I _really_ wanted to be able to give module signatures for all the common structures (stacks, queues, etc.) that I was going to be revisiting over and over. You can sort of do this in Haskell, but not cleanly.
* **Too esoteric/impractical.** Guilty as charged! I did try to point out a few data structures along the way that were especially practical, but that was not my main focus. If it was, I certainly would not have included umpteen different implementations of queues! Instead, I was trying to focus on design techniques, so that readers could use those techniques to design their own data structures. Many of the example data structures were included as illustrations of those design techniques, not because the examples were particularly practical or valuable by themselves.

### The Future?

People sometimes ask me if I'm planning a second edition. The answer is maybe, but not anytime soon. I'm still pretty happy with what I said and how I said it, so I don't feel a burning need to go back and correct things. If I wrote a second edition, it would be to modernize the presentation and to add some new data structures and techniques. For example, I might include the finger trees of Ralf Hinze and Ross Paterson.

In terms of the presentation, however, the biggest question would be what language to use. Standard ML probably doesn't make sense any more, but I'm still not sure Haskell is ready to take over, for the same reasons mentioned above. I suppose I could switch to OCaml, but I'm not sure that's enough of a change to warrant a new edition. I have faith that the vast majority of my readers are perfectly capable of making the translation from Standard ML to OCaml themselves.

Posted by  [ Chris Okasaki ][15] at  [1:08 PM][16] [ ![][17] ][18] [ ![][19] ][20]

Labels: [functional programming][21], [programming][22]

#### 31 comments:

![][23][ ][24]

[Jlouis][24] said... 
: 

This book is a gem.   
  
Thank you for spending the time putting the material together. 

:  [ February 8, 2008 at 2:26 PM ][25] [ ![][26] ][27]

![][28][ ][29]

[sharvil][29] said... 
: 

A few months ago, I started learning OCaml and got into a brief online discussion with a friend over immutable data structures. A few days later, I unexpectedly found a copy of your book on my doorstep courtesy of my friend.  
  
I opened the present with delight and immediately dropped everything else I was doing to dive into this fantastic view of data structures. I have come across few books that have been such a delight to read. When I thanked my friend for such a delightful gift, he mentioned that he, too, owns a copy and was just as excited reading it as I am.  
  
Thank you for such a concise, straightforward, and honest look at immutable data structures. 

:  [ February 8, 2008 at 3:38 PM ][30] [ ![][26] ][31]

![][32][ ][33]

[jeff][33] said... 
: 

Your book has been on my bookshelf for about as long as it has been in print and I've read it, reread it and consulted it off and on.   
  
A wonderful (and challenging) read that has taught me a lot. A book I recommend to my best students.   
  
Thanks. 

:  [ February 8, 2008 at 4:11 PM ][34] [ ![][26] ][35]

![][36][ ][37]

[calvin][37] said... 
: 

Haskell has recently become a lot more popular -- even within the last year -- and is poised to take a huge leap in popularity with the publishing of [Real-World Haskell][38] by O'Reilly.   
  
A newer edition of your book in Haskell, with some additional data structures, would have a _much_ larger audience than you currently have -- meaning lots more royalties, as well as having a much greater impact.  
  
**Please, please, pretty please!**

:  [ February 8, 2008 at 4:59 PM ][39] [ ![][26] ][40]

![][41][ ][42]

[Mietek][42] said... 
: 

Your book is used as a textbook for the Functional Algorithms and Data Structures course at the [Institute of Computer Science][43] of the University of Wrocław, Poland. We're quite big on functional programming over there. 

:  [ February 9, 2008 at 12:20 PM ][44] [ ![][26] ][45]

![][46][ ][47]

[sam][47] said... 
: 

Huh, I just bought your book recently. I only really briefly skimmed through most of it, but it seems like the amortized costs of laziness could be quite interesting. Is this a field that could be mined for much more material? 

:  [ February 9, 2008 at 3:47 PM ][48] [ ![][26] ][49]

![][50][ ][51]

[Chris Okasaki][51] said... 
: 

Mietek, thanks for the info. I'm curious, is this an undergraduate course or a graduate course?  
  
sam, it depends on what you mean by "mining", whether you mean finding more that's been written about it or doing more original research in the area. If the former, then not a lot. There have been a number of papers that have used the technique to analyze a particular implementation. There's also been some recent work on partially automating such analyses.  
  
If the latter, then sure, there's lots more that could be done! Practical time and space analyses that account for lazy evaluation are rather "thin on the ground" (to steal a phrase from my English friends). 

:  [ February 9, 2008 at 6:22 PM ][52] [ ![][26] ][53]

![][54][ ][55]

[Douglas][55] said... 
: 

First, thanks for the book, it's been a real education for me.  
  
Second _"... to this day, I don't know the correct name of the pattern"_.  
  
If it's the pattern shown on [ this Amazon page][56], I think it's an approximation to a [Sierpinski ][57] [Triangle][58]

:  [ February 10, 2008 at 5:35 PM ][59] [ ![][26] ][60]

![][50][ ][51]

[Chris Okasaki][51] said... 
: 

Douglas, it's definitely a close relative of the Sierpinski Triangle. I just wish I could find the name for the quilt pattern. Quilters always find much more colorful names than mathematicians. It's probably something like _Swallows Returning to Capistrano_ or _Ginkgo Leaves Falling_ or _Staggered Flight of B-2 Bombers_. Ok, maybe not the last one. 

:  [ February 11, 2008 at 11:23 AM ][61] [ ![][26] ][62]

![][63][ ![][64]][65]

[Geoff Knauth][65] said... 
: 

I got here via LtU. I'm one of those who bought the book after the Andrew Cooke review. I had no idea the book was so old (grin)--the ideas were all pretty new to me. Thank you for making a difficult subject enjoyable to read. 

:  [ February 11, 2008 at 6:41 PM ][66] [ ![][26] ][67]

![][50][ ][51]

[Chris Okasaki][51] said... 
: 

If you've ever wondered what this sort of thing would look like in a more mainstream language, Eric Lippert has just written part 11 in a huge series of posts about [immutability in C#][68]. 

:  [ February 13, 2008 at 12:20 AM ][69] [ ![][26] ][70]

![][71][ ][72]

[kHodel][72] said... 
: 

I did some Google-digging, and it looks like the inspiration for the book cover image is a variation of a quilt pattern called "Birds in the Air" (though it may go by other names as well). Here are a few links  
  
[birdsintheair2.pdf, from how-to-quilt.com][73]  
[flockofgeese.pdf, from how-to-quilt.com][74]  
[cover of a birds in the air quilt book][75]  
[the afore-mentioned book on amazon][76]  
[picture of a birds in the air quilt on a bed][77]

:  [ February 14, 2008 at 11:51 AM ][78] [ ![][26] ][79]

![][50][ ][51]

[Chris Okasaki][51] said... 
: 

kHodel, thank you! The second link lists Flying Geese as an alternate name for the pattern, so maybe that's why I was originally confused. (Flying Geese is usually the name for a more linear pattern of triangles.) 

:  [ February 14, 2008 at 11:58 AM ][80] [ ![][26] ][81]

![][82][ ![][83]][84]

[David][84] said... 
: 

I've liked _Purely Functional Data Structures_ for so long and for so much that I made it the subject of my first (and so far only) book review: [Persistent Data Structures - now (possibly) practical][85].  
  
I have just started on a Python implementation of the data structures. It would be a good language for a 2nd edition - popular, easy to read/understand (even if you don't know the language that well), and has the functional programming features needed (closures, polymorphism, GC). 

:  [ February 26, 2008 at 11:08 PM ][86] [ ![][26] ][87]

![][88][ ][89]

[s9][89] said... 
: 

Some of the more interesting algorithms (to me, at least) in Dr. Okasaki's book have fleshed out OCaml implementions in the Cf library of my hobby project on sourceforge.net. You can download [here][90]. There's also an impure, but still functional, persistent real-time, catenable deque that runs pretty fast. It was inspired by Dr. Okasaki's work on the more complicated purely functional variant. 

:  [ February 27, 2008 at 5:36 PM ][91] [ ![][26] ][92]

![][93][ ][94]

[caracarn11][94] said... 
: 

First let me say thank you for the book - it opened my eyes on what's possible.  
  
Second - I imagine legions of developers like me will thank you for a fuller treatment of hash table, either in an updated edition or blogs.  
  
The reason is - hash table is almost indispensible in many developers' day jobs since the internet revolution. The swiss army tool of data structures has shaped many developers' paradigm and it's simply difficult to see how things should and could be done otherwise.   
  
While not everyone of them are interested to enhance their skills, a small portion of this group are interested to learn the FP way, and it's simply hard to go from one paradigm to the other directly without a good bridge.   
  
A fuller functional hash table treatment, or a set of design principles to convert a imperative solution into a purely functional solutions would be *the* bridge for many of us who rely on hashtable every single day.  
  
So - maybe academically there are not much more to say about hash table, practically there are a lot to learn for us who are on the other side of the canyon looking over ;) 

:  [ June 12, 2008 at 5:48 PM ][95] [ ![][26] ][96]

![][97][ ][98]

[Alex Slesarenko][98] said... 
: 

I agree with caracarn11 that your book can help a lot on a way form imperative to FP world.   
  
Being an imperative C# programmer, I have always been interested in FP, so reсently I started to play with F#.  
I found it very natural way to functional world for .Net programmer.   
  
Luckily, [F# is about to be next mainstream language][99].   
  
I guess, F# is a language of a choice for Second Edition, since all examples can also be cross-compiled with OCaml. 

:  [ February 1, 2009 at 10:40 AM ][100] [ ![][26] ][101]

![][102][ ][103]

[George Colpitts][103] said... 
: 

I'd love to see a second version. One of the languages should still be Haskell, maybe the other could be Scala?  
  
I'd also like to see a section on graph data structures including a discussion of hybrid functional / imperative implementations. 

:  [ May 21, 2012 at 6:50 PM ][104] [ ![][26] ][105]

![][106][ ![][107]][108]

[Ning Ke][108] said... 
: 

Is there an implementation of the lazy notations used in the book? (the $ and lazy/force keyword) 

:  [ May 30, 2012 at 3:22 PM ][109] [ ![][26] ][110]

![][111][ ![][112]][113]

[jsalvati][113] said... 
: 

Do another version! 

:  [ August 23, 2012 at 2:54 PM ][114] [ ![][26] ][115]

![][116][ ![][117]][118]

[Ytzvan Mastino][118] said... 
: 

If you'll do another version, I hope you use Scala instead :D 

:  [ May 14, 2013 at 3:08 AM ][119] [ ![][26] ][120]

![][121][ ][122]

[test4242][122] said... 
: 

Hi,   
it is really a wounderful book. And it is really nice to read why  
you did not include the delete method for red-black-trees. Are  
you aware that the standard library of SML/NJ had a bug in delete  
operation that resulted in completely unbalanced red-black  
trees (more a linear list :-)). This bug can be trigged even with  
very small test cases, see, e.g., page 16 of "A.D. Brucker and  
B. Wolff, On Theorem Prover-based Testing. Formal Aspects of  
Computing. doi:10.1007/s00165-012-0222-y" for an example test  
case that triggers the bug. 

:  [ May 14, 2013 at 7:06 AM ][123] [ ![][26] ][124]

![][50][ ][51]

[Chris Okasaki][51] said... 
: 

@test4242: Interesting. I had not heard that about the SML/NJ library. 

:  [ May 14, 2013 at 8:48 AM ][125] [ ![][26] ][126]

![][127][ ][128]

[Luke Hoersten][128] said... 
: 

Chris, isn't it much more of a leap to pretend to have lazy evaluation extensions in ML or OCaml than it would be to use the real world facilities Haskell provides for specifying lazy vs. strict? Have you thought about contacting Simon Peyton Jones about some of your concerns to see what his thoughts are? I agree with some of the other commenters here that a Haskell edition would garner a much larger audience, again citing the success of Real-World Haskell. 

:  [ May 17, 2013 at 2:40 PM ][129] [ ![][26] ][130]

![][131][ ![][132]][133]

[Kejia Jiarui][133] said... 
: 

why not LISP? a canonical language survives decades. 

:  [ June 10, 2013 at 11:01 AM ][134] [ ![][26] ][135]

![][136][ ][137]

[STARRY][137] said... 
: 

I have been reading this book recently. It is really an insightful book. Thank you very much, Dr. Okasaki. Is the solutions to the exercises in the book available for download? 

:  [ June 10, 2014 at 8:19 AM ][138] [ ![][26] ][139]

![][50][ ][51]

[Chris Okasaki][51] said... 
: 

STARRY: No. However, many people have posted solutions to some of the problems. 

:  [ June 14, 2014 at 8:55 AM ][140] [ ![][26] ][141]

![][142][ ![][143]][144]

[Alexey Filippov][144] said... 
: 

I am trying to get through your book, re-implementing the examples and doing the exercises in Scala. As I’m doing that, I’ve encountered a typo which is most probably already known to you — but if it’s not (and since the books is seemingly printed on demand theses days), it won’t hurt sending it through:  
  
On page 133, the source of lookupTree contains the following clause:  
  
if i < w div 2 then lookupTree(w div 2, i - 1, t_1)  
else lookupTree(w div 2, i - 1 - w div 2, t_2)  
  
It’s easy to see that since the index in the tree is supposed to be from 0 to w - 1 (inclusive), the initial comparison must be i <= w div 2, lest the logic falls apart.  
  
The same typo repeats in Figure 9.7 on page 134  
  
Hope it helps — and thank you for the great book! 

:  [ November 15, 2015 at 12:12 PM ][145] [ ![][26] ][146]

![][50][ ][51]

[Chris Okasaki][51] said... 
: 

Alexey Filippov: Thanks. That does appear to be < on page 133, but the version on page 134 shows the <=. 

:  [ November 16, 2015 at 3:33 PM ][147] [ ![][26] ][148]

![][149][ ][150]

[NA][150] said... 
:  This comment has been removed by the author.

:  [ January 4, 2016 at 7:41 AM ][151] [ ![][26] ][152]

![][153][ ][150]

[Anonymous][150] said... 
: 

What's new in purely functional data structures since Okasaki?  
http://cstheory.stackexchange.com/q/1539/ 

:  [ January 5, 2016 at 5:32 AM ][154] [ ![][26] ][155]

[Post a Comment][156]

#### [][157][

[Newer Post][158] [Older Post][159] [Home][3]

Subscribe to: [Post Comments (Atom)][160]

## Blog Archive

* [ ►  ][161] [ 2013 ][162] (1)
    * [ ►  ][161] [ November ][163] (1)
* [ ►  ][161] [ 2011 ][164] (1)
    * [ ►  ][161] [ November ][165] (1)
* [ ►  ][161] [ 2010 ][166] (2)
    * [ ►  ][161] [ July ][167] (2)
* [ ►  ][161] [ 2009 ][168] (2)
    * [ ►  ][161] [ November ][169] (1)
    * [ ►  ][161] [ October ][170] (1)
* [ ▼  ][161] [ 2008 ][171] (28)
    * [ ►  ][161] [ October ][172] (1)
    * [ ►  ][161] [ September ][173] (2)
    * [ ►  ][161] [ July ][174] (4)
    * [ ►  ][161] [ June ][175] (1)
    * [ ►  ][161] [ May ][176] (5)
    * [ ►  ][161] [ April ][177] (4)
    * [ ►  ][161] [ March ][178] (5)
    * [ ▼  ][161] [ February ][179] (4)
        * [In praise of mandatory indentation for novice prog...][180]
        * [Games for Programmers: Zendo][181]
        * [Ten Years of Purely Functional Data Structures][182]
        * [Boolean Confusion][183]
    * [ ►  ][161] [ January ][184] (2)

[ ![][185] ][186]

## Labels

* [teaching][187]
* [programming][22]
* [games][188]
* [computational thinking][189]
* [functional programming][21]
* [creativity][190]
* [recursion][191]
* [TradeMaximizer][192]
* [failure][193]
* [food][194]
* [Ada][195]
* [Haskell][196]
* [algorithm][197]
* [algorithm in pictures][198]
* [crazy types][199]
* [induction][200]
* [kids][201]
* [math][202]
* [rant][203]
* [tournament][204]

[ ![][185] ][205]

## About Me

[ Chris Okasaki ][51]
[View my complete profile][51]

[ ![][185] ][206]

 

[1]: http://okasaki.blogspot.ru#main
[2]: http://okasaki.blogspot.ru#sidebar
[3]: http://okasaki.blogspot.ru/
[4]: http://www.cs.cmu.edu/~petel/
[5]: http://www.haskell.org/
[6]: http://en.wikipedia.org/wiki/Eddie_Haskell
[7]: http://www.smlnj.org/
[8]: http://citeseer.ist.psu.edu/117501.html
[9]: http://citeseer.ist.psu.edu/158610.html
[10]: http://citeseer.ist.psu.edu/okasaki95purely.html
[11]: http://books.slashdot.org/article.pl?no_d2=1&sid=04/02/19/2257203
[12]: http://www.topcoder.com/tc
[13]: http://jaortega.wordpress.com/2006/03/28/a-haskell-bookshelf/
[14]: http://www.amazon.com/gp/product/0521663504/
[15]: https://www.blogger.com/profile/18247315355264748920 "author profile"
[16]: http://okasaki.blogspot.ru/2008/02/ten-years-of-purely-functional-data.html "permanent link"
[17]: https://resources.blogblog.com/img/icon18_email.gif
[18]: https://www.blogger.com/email-post.g?blogID=2564777502681463717&postID=4783688804692941885 "Email Post"
[19]: https://resources.blogblog.com/img/icon18_edit_allbkg.gif
[20]: https://www.blogger.com/post-edit.g?blogID=2564777502681463717&postID=4783688804692941885&from=pencil "Edit Post"
[21]: http://okasaki.blogspot.ru/search/label/functional%20programming
[22]: http://okasaki.blogspot.ru/search/label/programming
[23]: http://lh3.googleusercontent.com/zFdxGE77vvD2w5xHy6jkVuElKv-U9_9qLkRYK8OnbDeJPtjSZ82UPq5w6hJ-SA%3Ds35 "Jlouis"
[24]: https://www.blogger.com/profile/02990737394952724516
[25]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1202498760000#c5482388442533974082 "comment permalink"
[26]: https://resources.blogblog.com/img/icon_delete13.gif
[27]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=5482388442533974082 "Delete Comment"
[28]: http://lh3.googleusercontent.com/zFdxGE77vvD2w5xHy6jkVuElKv-U9_9qLkRYK8OnbDeJPtjSZ82UPq5w6hJ-SA%3Ds35 "sharvil"
[29]: https://www.blogger.com/profile/10837472563653338726
[30]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1202503080000#c4407757674495187632 "comment permalink"
[31]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=4407757674495187632 "Delete Comment"
[32]: http://lh3.googleusercontent.com/zFdxGE77vvD2w5xHy6jkVuElKv-U9_9qLkRYK8OnbDeJPtjSZ82UPq5w6hJ-SA%3Ds35 "jeff"
[33]: https://www.blogger.com/profile/02233639532468393698
[34]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1202505060000#c6728864142419857491 "comment permalink"
[35]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=6728864142419857491 "Delete Comment"
[36]: http://lh3.googleusercontent.com/zFdxGE77vvD2w5xHy6jkVuElKv-U9_9qLkRYK8OnbDeJPtjSZ82UPq5w6hJ-SA%3Ds35 "calvin"
[37]: https://www.blogger.com/profile/01963831188473263515
[38]: http://www.realworldhaskell.org/blog/
[39]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1202507940000#c1011254504182353198 "comment permalink"
[40]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=1011254504182353198 "Delete Comment"
[41]: http://lh3.googleusercontent.com/zFdxGE77vvD2w5xHy6jkVuElKv-U9_9qLkRYK8OnbDeJPtjSZ82UPq5w6hJ-SA%3Ds35 "Mietek"
[42]: https://www.blogger.com/profile/05245796149619242061
[43]: http://www.ii.uni.wroc.pl/
[44]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1202577600000#c8341041038808572389 "comment permalink"
[45]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=8341041038808572389 "Delete Comment"
[46]: http://lh3.googleusercontent.com/zFdxGE77vvD2w5xHy6jkVuElKv-U9_9qLkRYK8OnbDeJPtjSZ82UPq5w6hJ-SA%3Ds35 "sam"
[47]: https://www.blogger.com/profile/09927743629478997946
[48]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1202590020000#c6354531547387214091 "comment permalink"
[49]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=6354531547387214091 "Delete Comment"
[50]: http://lh3.googleusercontent.com/zFdxGE77vvD2w5xHy6jkVuElKv-U9_9qLkRYK8OnbDeJPtjSZ82UPq5w6hJ-SA%3Ds35 "Chris Okasaki"
[51]: https://www.blogger.com/profile/18247315355264748920
[52]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1202599320000#c5147467442853225787 "comment permalink"
[53]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=5147467442853225787 "Delete Comment"
[54]: http://lh3.googleusercontent.com/zFdxGE77vvD2w5xHy6jkVuElKv-U9_9qLkRYK8OnbDeJPtjSZ82UPq5w6hJ-SA%3Ds35 "Douglas"
[55]: https://www.blogger.com/profile/04517193778611033674
[56]: http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504
[57]: http://images.google.com/images?q=sierpinski+triangle
[58]: http://en.wikipedia.org/wiki/Sierpinski_triangle
[59]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1202682900000#c2784969031921737393 "comment permalink"
[60]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=2784969031921737393 "Delete Comment"
[61]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1202746980000#c7680748084551971620 "comment permalink"
[62]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=7680748084551971620 "Delete Comment"
[63]: https://img1.blogblog.com/img/blank.gif "Geoff Knauth"
[64]: http://knauth.org/gsk/images/gsk-pa2000-48x48.jpg
[65]: https://www.blogger.com/profile/12025560607512616605
[66]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1202773260000#c6875646046054067122 "comment permalink"
[67]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=6875646046054067122 "Delete Comment"
[68]: http://blogs.msdn.com/ericlippert/archive/2008/02/12/immutability-in-c-part-eleven-a-working-double-ended-queue.aspx
[69]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1202880000000#c162261019822490271 "comment permalink"
[70]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=162261019822490271 "Delete Comment"
[71]: http://lh3.googleusercontent.com/zFdxGE77vvD2w5xHy6jkVuElKv-U9_9qLkRYK8OnbDeJPtjSZ82UPq5w6hJ-SA%3Ds35 "kHodel"
[72]: https://www.blogger.com/profile/02232620214904583773
[73]: http://www.how-to-quilt.com/patterns/birdsintheair2.pdf
[74]: http://www.how-to-quilt.com/patterns/flockofgeese.pdf
[75]: http://www.onestitchatatime.com/images/BookbirdsintheAir.jpg
[76]: http://www.amazon.com/Birds-Air-Quilt-Eleanor-Burns/dp/189177607X
[77]: http://www.amishcountrylanes.com/Pages/hs140.shtml
[78]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1203007860000#c8920988804513035736 "comment permalink"
[79]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=8920988804513035736 "Delete Comment"
[80]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1203008280000#c4010672848726391886 "comment permalink"
[81]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=4010672848726391886 "Delete Comment"
[82]: https://img1.blogblog.com/img/blank.gif "David"
[83]: http://photos1.blogger.com/img/122/6879/640/davidbak-1.jpg
[84]: https://www.blogger.com/profile/09358968282816697343
[85]: http://bakins-bits.com/archives/4
[86]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1204085280000#c1808588102521315137 "comment permalink"
[87]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=1808588102521315137 "Delete Comment"
[88]: http://lh3.googleusercontent.com/zFdxGE77vvD2w5xHy6jkVuElKv-U9_9qLkRYK8OnbDeJPtjSZ82UPq5w6hJ-SA%3Ds35 "s9"
[89]: https://www.blogger.com/profile/08326725206530909278
[90]: http://sf.net/projects/ocnae
[91]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1204151760000#c7313910542668793968 "comment permalink"
[92]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=7313910542668793968 "Delete Comment"
[93]: http://lh3.googleusercontent.com/zFdxGE77vvD2w5xHy6jkVuElKv-U9_9qLkRYK8OnbDeJPtjSZ82UPq5w6hJ-SA%3Ds35 "caracarn11"
[94]: https://www.blogger.com/profile/11915946249340014269
[95]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1213307280000#c2474351609339300596 "comment permalink"
[96]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=2474351609339300596 "Delete Comment"
[97]: http://lh3.googleusercontent.com/zFdxGE77vvD2w5xHy6jkVuElKv-U9_9qLkRYK8OnbDeJPtjSZ82UPq5w6hJ-SA%3Ds35 "Alex Slesarenko"
[98]: https://www.blogger.com/profile/10253205349391319347
[99]: http://blogs.msdn.com/dsyme/archive/2008/12/10/fsharp-to-ship-as-part-of-visual-studio-2010.aspx
[100]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1233502800000#c5455570747173997121 "comment permalink"
[101]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=5455570747173997121 "Delete Comment"
[102]: http://lh3.googleusercontent.com/zFdxGE77vvD2w5xHy6jkVuElKv-U9_9qLkRYK8OnbDeJPtjSZ82UPq5w6hJ-SA%3Ds35 "George Colpitts"
[103]: https://www.blogger.com/profile/15526399395097722268
[104]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1337640613592#c5174294761091495853 "comment permalink"
[105]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=5174294761091495853 "Delete Comment"
[106]: https://img1.blogblog.com/img/blank.gif "Ning Ke"
[107]: http://4.bp.blogspot.com/-QgHWnh04f1E/TtoLvoxR_GI/AAAAAAAAAXk/USeTH9-goSM/s35/IMG_0278_modified.JPG
[108]: https://www.blogger.com/profile/04382088443772501731
[109]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1338405768859#c2722744211835308594 "comment permalink"
[110]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=2722744211835308594 "Delete Comment"
[111]: https://img1.blogblog.com/img/blank.gif "jsalvati"
[112]: http://4.bp.blogspot.com/_d8cOY8m-DOQ/SaqFTZpGdaI/AAAAAAAAAA0/DdO6itY3MMM/S45-s35/mymohawkprofilepicmm6.jpg
[113]: https://www.blogger.com/profile/16509764680257537430
[114]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1345748066193#c5549836543865012630 "comment permalink"
[115]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=5549836543865012630 "Delete Comment"
[116]: https://img1.blogblog.com/img/blank.gif "Ytzvan Mastino"
[117]: http://1.bp.blogspot.com/-RSaeCG2aWs4/T6AoCM9ulZI/AAAAAAAAB_k/8HvE0QYyiqw/s35/IMG_20120419_143515.jpg
[118]: https://www.blogger.com/profile/02839427927798159628
[119]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1368515298532#c1485356220649928985 "comment permalink"
[120]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=1485356220649928985 "Delete Comment"
[121]: http://lh3.googleusercontent.com/Rw_wdkZHfDXh8tDEBFF1Q3aSS_nDE-gMVWNfOHb7a2nIp2XuWAmJyGISHv9akZE%3Ds35 "test4242"
[122]: http://test4242.myopenid.com/
[123]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1368529609825#c8240543527365753368 "comment permalink"
[124]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=8240543527365753368 "Delete Comment"
[125]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1368535691521#c506141857385715837 "comment permalink"
[126]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=506141857385715837 "Delete Comment"
[127]: http://lh3.googleusercontent.com/Rw_wdkZHfDXh8tDEBFF1Q3aSS_nDE-gMVWNfOHb7a2nIp2XuWAmJyGISHv9akZE%3Ds35 "Luke Hoersten"
[128]: http://luke.hoersten.org/
[129]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1368816030984#c1549559973933376571 "comment permalink"
[130]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=1549559973933376571 "Delete Comment"
[131]: https://img1.blogblog.com/img/blank.gif "Kejia Jiarui"
[132]: http://lh3.googleusercontent.com/-IhqmwH3NzK8/AAAAAAAAAAI/AAAAAAAAAvQ/hQYtYy9wQEo/s35-c/photo.jpg
[133]: https://www.blogger.com/profile/09118109916964096210
[134]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1370876468659#c4900609800837005691 "comment permalink"
[135]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=4900609800837005691 "Delete Comment"
[136]: http://lh3.googleusercontent.com/zFdxGE77vvD2w5xHy6jkVuElKv-U9_9qLkRYK8OnbDeJPtjSZ82UPq5w6hJ-SA%3Ds35 "STARRY"
[137]: https://www.blogger.com/profile/16814037505220054868
[138]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1402402778024#c4723555374493555399 "comment permalink"
[139]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=4723555374493555399 "Delete Comment"
[140]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1402750535449#c560041156084751911 "comment permalink"
[141]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=560041156084751911 "Delete Comment"
[142]: https://img1.blogblog.com/img/blank.gif "Alexey Filippov"
[143]: http://lh5.googleusercontent.com/-N-0nrK109Bw/AAAAAAAAAAI/AAAAAAAAENE/0sKyZzumjWE/s35-c/photo.jpg
[144]: https://www.blogger.com/profile/13208800385701081197
[145]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1447607536945#c8605583546519509656 "comment permalink"
[146]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=8605583546519509656 "Delete Comment"
[147]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1447705984743#c6931993576278299389 "comment permalink"
[148]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=6931993576278299389 "Delete Comment"
[149]: http://lh3.googleusercontent.com/zFdxGE77vvD2w5xHy6jkVuElKv-U9_9qLkRYK8OnbDeJPtjSZ82UPq5w6hJ-SA%3Ds35 "NA"
[150]: https://www.blogger.com/profile/06835703169605180863
[151]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1451911270252#c4133734024049485140 "comment permalink"
[152]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=4133734024049485140 "Delete Comment"
[153]: http://lh3.googleusercontent.com/zFdxGE77vvD2w5xHy6jkVuElKv-U9_9qLkRYK8OnbDeJPtjSZ82UPq5w6hJ-SA%3Ds35 "Anonymous"
[154]: http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html?showComment=1451989976264#c5666426883128303303 "comment permalink"
[155]: https://www.blogger.com/delete-comment.g?blogID=2564777502681463717&postID=5666426883128303303 "Delete Comment"
[156]: https://www.blogger.com/comment.g?blogID=2564777502681463717&postID=4783688804692941885
[157]: 
[158]: http://okasaki.blogspot.ru/2008/02/games-for-programmers-zendo.html "Newer Post"
[159]: http://okasaki.blogspot.ru/2008/02/boolean-confusion.html "Older Post"
[160]: http://okasaki.blogspot.com/feeds/4783688804692941885/comments/default
[161]: javascript:void(0)
[162]: http://okasaki.blogspot.ru/2013/
[163]: http://okasaki.blogspot.ru/2013/11/
[164]: http://okasaki.blogspot.ru/2011/
[165]: http://okasaki.blogspot.ru/2011/11/
[166]: http://okasaki.blogspot.ru/2010/
[167]: http://okasaki.blogspot.ru/2010/07/
[168]: http://okasaki.blogspot.ru/2009/
[169]: http://okasaki.blogspot.ru/2009/11/
[170]: http://okasaki.blogspot.ru/2009/10/
[171]: http://okasaki.blogspot.ru/2008/
[172]: http://okasaki.blogspot.ru/2008/10/
[173]: http://okasaki.blogspot.ru/2008/09/
[174]: http://okasaki.blogspot.ru/2008/07/
[175]: http://okasaki.blogspot.ru/2008/06/
[176]: http://okasaki.blogspot.ru/2008/05/
[177]: http://okasaki.blogspot.ru/2008/04/
[178]: http://okasaki.blogspot.ru/2008/03/
[179]: http://okasaki.blogspot.ru/2008/02/
[180]: http://okasaki.blogspot.ru/2008/02/in-praise-of-mandatory-indentation-for.html
[181]: http://okasaki.blogspot.ru/2008/02/games-for-programmers-zendo.html
[182]: http://okasaki.blogspot.ru/2008/02/ten-years-of-purely-functional-data.html
[183]: http://okasaki.blogspot.ru/2008/02/boolean-confusion.html
[184]: http://okasaki.blogspot.ru/2008/01/
[185]: https://resources.blogblog.com/img/icon18_wrench_allbkg.png
[186]: //www.blogger.com/rearrange?blogID=2564777502681463717&widgetType=BlogArchive&widgetId=BlogArchive1&action=editWidget&sectionId=sidebar "Edit"
[187]: http://okasaki.blogspot.ru/search/label/teaching
[188]: http://okasaki.blogspot.ru/search/label/games
[189]: http://okasaki.blogspot.ru/search/label/computational%20thinking
[190]: http://okasaki.blogspot.ru/search/label/creativity
[191]: http://okasaki.blogspot.ru/search/label/recursion
[192]: http://okasaki.blogspot.ru/search/label/TradeMaximizer
[193]: http://okasaki.blogspot.ru/search/label/failure
[194]: http://okasaki.blogspot.ru/search/label/food
[195]: http://okasaki.blogspot.ru/search/label/Ada
[196]: http://okasaki.blogspot.ru/search/label/Haskell
[197]: http://okasaki.blogspot.ru/search/label/algorithm
[198]: http://okasaki.blogspot.ru/search/label/algorithm%20in%20pictures
[199]: http://okasaki.blogspot.ru/search/label/crazy%20types
[200]: http://okasaki.blogspot.ru/search/label/induction
[201]: http://okasaki.blogspot.ru/search/label/kids
[202]: http://okasaki.blogspot.ru/search/label/math
[203]: http://okasaki.blogspot.ru/search/label/rant
[204]: http://okasaki.blogspot.ru/search/label/tournament
[205]: //www.blogger.com/rearrange?blogID=2564777502681463717&widgetType=Label&widgetId=Label1&action=editWidget&sectionId=sidebar "Edit"
[206]: //www.blogger.com/rearrange?blogID=2564777502681463717&widgetType=Profile&widgetId=Profile1&action=editWidget&sectionId=sidebar "Edit"

  [*[1:08 PM]: 2008-02-08T13:08:00-05:00

