Purely Functional Data Structures 427
| Purely Functional Data Structures | |
| author | Chris Okasaki |
| pages | 220 |
| publisher | Cambridge University Press |
| rating | 8/10 |
| reviewer | Andrew Cooke |
| ISBN | 0521663504 |
| summary | Functional programming for grown-ups. |
In Okasaki's introduction he says that the "[...] benefits of functional languages are well known, but still the vast majority of programs are written in imperative languages such as C. This apparent contradiction is easily explained by the fact that functional languages have historically been slower than their more traditional cousins, but this gap is narrowing."
Indeed, OCaml has a reputation for being "as fast as C," yet it contains automatic memory management and supports object-oriented, as well as functional, programming. It's also probably the most widely used functional language outside academia (except perhaps Lisp/Scheme).
I mention OCaml not just because it's fast, free and popular, but because Okasaki uses a related language - ML - in his book. The ML family of languages are the standard strict, functional languages (Standard ML of New Jersey is perhaps the reference implementation but see also standardml.org). Okasaki also includes an appendix with examples in Haskell, which is the standard lazy functional language.
The difference between lazy and strict languages is the order in which code is evaluated. Most languages are strict. Unlike most languages, Haskell only evaluates something when it is absolutely necessary. Each parameter to a function, for example, is passed as a "thunk" of code, not a value. If the value is not required inside the function, the parameter is left unused; if it is required (say as part of a result that needs to be displayed) then the thunk is evaluated. This evaluation may trigger a whole slew of evaluations of functions that "should" have been called earlier (from a Java programmer's point of view).
Laziness is both good and bad. The bad side is obvious: the order in which code is executed my be very different from the order in which the program was written and some serious book-keeping is necessary in the compiler to juggle the thunks of code and their final values. The reordering of code could cause mayhem for IO operations, for example (in practice, of course, Haskell includes a solution to this problem).
The good side is that laziness can help make programs more efficient and, while the definition of ML doesn't include laziness, individual ML implementations -- including OCaml and SML/NJ -- include it as an extra.
Much of Purely Functional Data Structures (the second of three parts) focuses on how to use laziness to make data structures efficient. Lazy evaluation allows book-keeping actions to be postponed, for example, so that the cost of maintaining the data structure in an efficient form can be averaged across several read/write operations (improving worst case limits - avoiding a very slow response if the data happen to be in a "bad" order).
An understanding of how the efficiency of algorithms is rated (the big-O notation) is one piece of knowledge that this book does assume, along with a basic grasp of what Stacks, Queues, Trees, etc, are.
This lazy boost in efficiency is needed because, even though functional languages may be getting faster, it's not always possible for them to implement the efficient algorithms used in imperative (non-functional) programming.
But I'm getting ahead of myself, because I haven't described what a functional language is, or why it is useful. These are the topics of the first part of the book, which explains how functional languages, which make it impossible to change variable values by direct assignment, support persistent data structures. This section is fairly brief, and while it's a good refresher course for someone who's not had to worry about such things since studying at university, it's not sufficient as an initial introduction to functional programming in general.
There's a good explanation of functional programming in the Wikipedia, but, in all honesty, I don't see how anyone can really "get it" without writing functional code (just as I, at least, couldn't understand how OOP worked until I wrote code that used objects).
So forgive me for not telling you why functional programming is good (This paper is one famous attempt), but perhaps a better question to focus on is "Why should you spend the time to investigate this?" The best answer I can give is that it leads to a whole new way of thinking about programming. Describing functional programming as "excluding assignment to variables" doesn't do justice to the consequences of such a profound change (one I found almost unimaginable - how can you program without loop counters, for example?).
There's a practical side to all this too - learning new ways of thinking about programs makes you a better programmer. This ties in closely with the final part of Okasaki's book, which explores a few fairly esoteric approaches to data structures. Who would have thought that you can design data structures that parallel the way in which you represent numbers? Some of this is pretty heavy going - I can't say I understood it all, but I'm taking this book with me on holiday (it's slim - just over 200 pages) and I'll be bending my brain around some of the points in the last few chapters as I lie in the sun (here in the southern hemisphere it's late summer).
So just who would benefit from this book? It seems to me that it's most valuable as a second book on functional programming. There are a bunch of texts (and online guides) that can get you started in functional programming. This one goes further. It shows how to exploit the features of functional languages to solve real problems in applied computing. Admittedly, they are problems that have already been solved in imperative languages, but you might find that you, too, come to enjoy those famous benefits of functional languages. The algorithms in this book let you enjoy those benefits without paying the price of inefficiency.
Andrew Cooke last reviewed for Slashdot The Aardvark is Ready for War . You can purchase Purely Functional Data Structures from bn.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.
Re:This was a great review (Score:5, Insightful)
For example, where I work, I have to write in ColdFusion sometimes. ColdFusion has 2 syntaxes: a tag-based one that looks like HTML and is four times redudant and impossible to deal with, but is easier for people, and a second syntax with first-order functions. Writing in the first-order function syntax is easier, more efficient, clearer, and easier to debug in everyway, except all my co-workers write in the tag syntax, which forces me to, as well. It sucks.
The point is that programs tend to be written to the lower-common-demoninator of the language, which makes the difference between functional, procedural, and oo languages so huge when there is really no difference.
The memories... (Score:5, Insightful)
Re:Nice Review! (Score:1, Insightful)
I hate to disagree, but I don't feel there was a lot of content. I'm very interested in functional programming and would have liked to know what sort of topics are covered in the book and get a sneak peak at the "how-to" behind representing data structures in a purely functional language. Instead I got an introduction to lazy functional languages followed by an introduction to functional languages. Good material, to be sure, but about the only thing I got on the book's specific content was that it requires you to know big-O notation and has an introduction to functional languages that really doesn't completely suffice if you've never seen functional programming before.
Re:Functionals (Score:5, Insightful)
I don't know how you can say that the languages are more complicated. Scheme, for example, is the simplest language I know of, in terms of syntax and semantics.
I think you're confusing this with how difficult it is to think functionaly when you've been raised to think imperatively. Functional programming is a different paradigm than imperative programming, and as such, you have to think differently. If you've been programming imperatively for a while, learning another imperative langauge is often straight forward; you learn the basics of the syntax, what the language provides natively, and how you can construct what it does not provide. You already know how to solve problems with that style of language.
Learning a functional language, however, is more than just having to learn a different syntax and set of rules (assuming you've been raised imperatively). You have to learn a different way of solving problems. And until you've done that for quite some time (I, for example, have not), I don't think you're qualified to make the judgement calls you did.
Re:Purely *Functional* Data Structures (Score:5, Insightful)
Then how the heck do you know what the teachers are teaching? Maybe you have only talked to the morons who go through comp-sci thinking it is a programming degree. I know that there was a large percentage of people I went through school with who chose to ignore things like functional programming simply because they had the mind set that they were there to get a software development job after school. It was taught, but it mostly fell on deaf ears. If it wasn't c++/MFC they thought they wouldn't need it (and hence spent no time trying to learn it). They were the same crop of students who thought it was stupid that they had to take differential equations and physics, because they would never use that in "the field." They just wasted their education.
I personally thought it was really interesting, and as such I am now a graduate student. I love comp-sci for what it actually is, which is not programming.
Why am I replying to a troll??? Oh well, I feel better now.
Re:The memories... (Score:3, Insightful)
With Monadic programming in a purely lazy functional programming language like Haskell, you can place print statements in your code for debugging... though such a practice isn't even considered good in imperative programming, let alone functional programming.
Also, since languages like Haskell are pure, adding print statements into your code will most likely change the various types of functions. In other words, a function that returns an integer and a function that returns an integer and prints something - both such functions have different types in Haskell.
It is easy to debug functional programs, if you have a trace debugger, i.e. a debugger that shows the evaluation step by step and lets you skip evaluation of subexpressions.
Please give me an explicit example as to why lazy programs are difficult to debug.
A coder's hobby (Score:3, Insightful)
So this is what computer programmers do in their spare time - program computers! WooHoo!
Re:Functionals (Score:5, Insightful)
You know how they say, once you know one programming language, learning another is easy? Yes, once you know C++, picking up Java is a sinch, and you can probably even read someone's Python code without even learning the language first. But, this is because all of these languages are imperative. If someone tells you to write something in LISP, you may be able to figure out the syntax pretty easily, but no doubt you'll find yourself using imperative constructs like "progn". And, when you do that, the language seems very difficult to use indeed, because it was never supposed to be used that way. I made this mistake once myself.
Anyway, point is, it's not really fair for you to be judging functional languages until you've practiced them as much as the imperative ones. Personally, my imperative experience still dwarfs my functional experience by a factor of thousands... but I've now convinced myself that, for most purposes, functional languages are superior.
Re:Functionals (Score:5, Insightful)
but speaking as a coder who learned functional programming just last year in class, I can say that functional languages are a lot more complicated than procedural languages.
Wouldn't you be a little bit more qualified to comment if you had several years of experience with both functional and imperative languages, first?
Re:The memories... (Score:3, Insightful)
The difficulty of debugging scheme arises from the fact that it isn't a statically typed language. Errors such as trying to get the cdr of an atom are caught only at runtime (unless you've got some sort of "soft" typing as done in Dr. Scheme environments, for example). As opposed to this, Caml/SML/Haskell are typed languages, and that avoids a major source of errors and debugging. Once you're past the typechecker, the errors are all logical (no programming language can help you there).
As for difficulty to reason about, well, notwithstanding the claims of FP coders that all FP programs are self-documenting, it can get quite difficult once you have to deal with higher-order functions that have escaping values. Functional programming is often combinator heavy and trying to read someone elses code is not always easy (I don't have an equal amount of experience with
OO/Procedural/Functional paradigms to give a sensible comparison).
Re:Purely *Functional* Data Structures (Score:4, Insightful)
Knowing what the term means, and knowing how to actually prove that an algorithm is O(x), are two different things. Can you prove that general sorting cannot be less than O(n log n)? This is fundamental. If you can't do it, you do not know computer science. (Flip side of coin: if you can, then you are at least heading the right direction).
"game programming is not real comp-sci!" (tell that to my collision algorithms or research into better timing methods)
A hobbyist tinkering in the garage does not a scientist make. Put out a publication comparing your methods with other known methods. Give theoretical upper and lower bounds on run time, memory usage, jitter, etc. Criticize yourself and explain the defects in your methods. Submit it to peer scrutiny. That's science.
Re:Functional Programming missed the boat (Score:5, Insightful)
Also, it's not exactly true that functional programming lacks a big-name sponsor. Haskell research and implementation is largely driven by Microsoft Research. This is not the same as promoting (something like) Haskell to working programmers, but it suggests that Microsoft has its eye on doing so someday.
Re:A coder's hobby (Score:3, Insightful)
You should qualify that; it's what good programmers do in their spare time.
"Thank ye, Sir! It'll give me time to catch up on my technical journals!" --Lt. Cmdr. Montgomery Scott, "The Trouble with Tribbles," ST:TOS
Re:Nice Review! (Score:3, Insightful)
I don't see how it's "flamebait" or "troll." Apparently functional programmers can't see past "defense of the functional paradigm of programming."
Don't you understand? I want to be one of you; I want to be a functional programmer. I want to know what this book is about and if it can help me get into functional programming. I already know there's something special and wonderful to be gained from the functional paradigm. I don't need an introduction to functional programming or a defense of its merits. What I need is a description of what's in this book. (My thanks to the user who posted the book's table of contents. That was far better than the review.)
I guess some folks are so busy dividing up the world into "friends" and "enemies" that they can't figure out how to just provide information. Obviously, since I didn't rave about how great the review was, I must be an enemy of functional programming and deserve to be modded down.
How can this review be so great when the reviewer didn't even talk about the book? I'd probably willingly agree the book was great if I could know what was in it, but this review told me next to nothing. The people who've said the review is great are really commenting on the quality of the book, not the review; almost all of them say they've already got it.
Re:XSLT (Score:1, Insightful)
In fact, there are no second nor third class functions in XSTL, only templates, which are more alike procedures than functions (cause they don't return useful result - except for dumping it to output stream)