Become a fan of Slashdot on Facebook

 


Forgot your password?
Close
typodupeerror
×
Programming Books Data Storage Media Book Reviews IT Technology

Purely Functional Data Structures 427

Posted by timothy from the raw-function-baby dept.
andrew cooke writes "A while ago I read the comments following a Slashdot book review. Someone had posted a request for books that covered a wider range of languages than Java, C, Python, etc. Well, I thought, why not review Okasaki's Purely Functional Data Structures? It's a classic from the underworld of functional programming - recognised as the standard reference, yet clear enough to work as an introduction to the subject for anyone with a basic functional programming background. Of course, some readers won't know what functional programming is, or what is special about pure data structures. So I hope that this review can also serve as something of an introduction to the languages that I (a software engineer paid to work with Java, C, Python, etc) choose to use in my spare time, just for the joy of coding." Read on for the rest; even if you're not planning to give up C or Perl, there are links here worth exploring.
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.
This discussion has been archived. No new comments can be posted.

Purely Functional Data Structures More

Purely Functional Data Structures

Comments Filter:

  • Purely *Functional* Data Structures (Score:4, Funny)

    by Orne ( 144925 ) on Wednesday March 03, 2004 @01:05PM (#8453687) Homepage
    As opposed to what, Data Structures that don't work? Yeah, we need more books on those...

    • Re:Purely *Functional* Data Structures (Score:5, Funny)

      by MooseByte ( 751829 ) on Wednesday March 03, 2004 @01:09PM (#8453737)

      "As opposed to what, Data Structures that don't work? Yeah, we need more books on those..."

      Fear not, MFC is extensively documented.

      (Complains I, recently bit by yet another lame long-acknowledged-yet-unfixed bug in M$'s class libraries.)

    • Have you tried Microsoft Press?

    • Re:Purely *Functional* Data Structures (Score:2, Informative)

      by Anonymous Coward
      As opposed to what

      Just to make sure everyone knows, it's as opposed to imperative data structures. "Imperative" refers to code that works through updating variables. OO languages such as Java and C++, and languages like C and Pascal are imperative. "Functional languages" do not support updatable variables.

  • Over where I work (Score:5, Funny)

    by Anonymous Coward on Wednesday March 03, 2004 @01:05PM (#8453693)
    Management prefers dysfunctional programming.

  • I don't even see the code.. (Score:5, Funny)

    by laurent420 ( 711504 ) on Wednesday March 03, 2004 @01:06PM (#8453697)
    blonde... brunette..
    • Did the mods miss it? It's not exactly offtopic, if you get the context right. The line was from somebody examining DATA STRUCTURES representing people in the "Matrix", remarking that after a certain period of time, he stopped classifying them conciously and started seeing "blond, brunette".

      I suppose he is implying that this book would be of no use to him.

      Is that enough explanation? Jesus Christ.

  • Nice Review! (Score:5, Informative)

    by jaaron ( 551839 ) on Wednesday March 03, 2004 @01:06PM (#8453700) Homepage
    Nice to see some actual content on Slashdot!

    By the way, this reminds me of the recent article on Domain Specific Languages over on Martin Foweler's website [martinfowler.com]. Another aspect of programming worth investigating.

  • O'Camel (Score:4, Interesting)

    by Robert Webb ( 172183 ) <robert@robertwebb.com> on Wednesday March 03, 2004 @01:07PM (#8453709) Homepage
    Is 'OCaml' pronounced 'Oh-Camel', 'Ach-amel'...? Akin to the 'Line-Ux' versus 'Lin-Ux' confusion.

  • At first I read the headline as "Purely Fictional Data Structures."
    I was really confused for a minute thinking, "What do ficticious data structures have to do with ML or Lisp?"

  • Not a typewriter (Score:5, Funny)

    by JoshuaDFranklin ( 147726 ) <joshuadfranklin...NOSPAM@@@yahoo...com> on Wednesday March 03, 2004 @01:07PM (#8453714) Homepage
    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...

    You know, your computer is not a typewriter [princeton.edu], so you really could have rewritten that part of your review...

  • I like any language (Score:5, Funny)

    by donnyspi ( 701349 ) <junk5&donnyspi,com> on Wednesday March 03, 2004 @01:09PM (#8453734) Homepage
    that supports GOTOs. Those are the best!

  • Functionals (Score:3, Interesting)

    by SparafucileMan ( 544171 ) on Wednesday March 03, 2004 @01:10PM (#8453753)
    Functional languages fucking 0wn. They are, generally, easier to write, maintain, read, understand, and debug than the procedural nonsense that has dominated programming (due solely to the historical problems of making computers fast and having nothing to do with best theoretical practices). Now, if someone would just re-start production of LISP machines (updated for modern functional languages), nearly all of us would be better off.

    • Re:Functionals (Score:4, Interesting)

      by ill_mango ( 686617 ) on Wednesday March 03, 2004 @01:19PM (#8453854)
      Are you serious?

      I agree that functional programming languages are quite useful, 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.

      Sure, once you get good at it you can bang out a functional program easily, and maintenance can be a breeze once you know how to write the code. However, reading and understanding code that ISN'T yours can be damn near impossible sometimes, especially when you're a newbie.

      I'm not discounting the use of functional languages, I'm just saying they are harder to learn than procedural languages.

      • Re:Functionals (Score:4, Informative)

        by SparafucileMan ( 544171 ) on Wednesday March 03, 2004 @01:26PM (#8453930)
        Its a different mind-set required to write in a functional language, that's all. Some people find it a steeper learning curve, and some don't. But the effort put into learning the functional language style will be paid back 1,000 fold (at least) for the rest of your life, whereas learning a typical procedural language will only get you 10x return. Plus the pay-back on learning the functional language will apply to _all_ languages you ever learn. This is because all languages and algorithms are defined, on paper, in a functional style anyway (since it uses "math"), and the procedural super-set is just a needless complication from what is 'really happening'.

        But then again, I majored in math, not programming, so maybe I'm biased.

      • Re:Functionals (Score:5, Insightful)

        by Kupek ( 75469 ) on Wednesday March 03, 2004 @01:35PM (#8454026)
        I agree that functional programming languages are quite useful, 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.

        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:Functionals (Score:3, Interesting)

        by Arcanix ( 140337 )
        Of course they are harder for you to learn. I had the same problem, we were both taught first on an imperative language and so forever more we are stuck on that mindset.

        People I have met who started out on functional and can write a lisp program as quick as I can write C often have serious problems with even the simplest program imperative languages just as I will get stumped by something stupid when trying to use lisp.

        As in natural languages it is normally your first language that you are going to be

      • However, reading and understanding code that ISN'T yours can be damn near impossible sometimes, especially when you're a newbie.

        That's a bit harsh! Isn't this true of all programming languages?

        Think of it this way, because there is much less code to write, and you shave off all the fluff and get to the point, surely that makes the code easier to read, because you're not left scratching your head and asking why certain counters are included, what a variable is set as at any one point in the program (this i

      • Re:Functionals (Score:5, Insightful)

        by Temporal ( 96070 ) on Wednesday March 03, 2004 @01:44PM (#8454141) Journal
        If you only just learned it last year in class, no wonder you find it complicated. You probably have much more experience with imperative languages. Indeed, when you think about programming, your thoughts are probably imperative. Just as a native English speaker might think Japanese is complicated (even after "learning it in class last year"), a native imperative programmer will find functional programming difficult at first.

        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)

        by Anonymous Coward on Wednesday March 03, 2004 @01:45PM (#8454145)

        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?

      • I can say that functional languages are a lot more complicated than procedural languages.

        Which functional languages are more complicated than which procedural ones? Scheme is a lovely, simple, tiny little language -- I have a hard time envisioning a simpler language. Haskell is also quite compact.

        And in addition, I think that pure functional programs are much less complicated and full of crufty overhead than procedural ones. It's the whole "describe the problem" rather than "describe the solution" app

      • Re:Functionals (Score:5, Informative)

        by gangien ( 151940 ) on Wednesday March 03, 2004 @01:50PM (#8454197) Homepage
        I can say that functional languages are a lot more complicated than procedural languages

        What?? More complicated? No no no.. They are certainly not more complicated. For instance the funcitonal languages:

        (display "Hello World") -Scheme

        main =
        do
        putStr "Hello World" - Haskell

        vs

        #include
        main () {
        printf("hello world"); }- C

        #!/usr/bin/perl
        print "hello world"; - perl

        Now those differences are subtle, but A. The functional languages are easier to read(and I think most any none biases person would aggree with me) B. No whacky syntax, hell scheme syntax is only () C. The data types are simple, Pointers? please. Ect ect. The thing that makes functional programming difficult is the lack of an imperative control flow. Which is how people tend to solve problems. For instance if you want to sum up the numbers 1 through 8, in an imperative language it'd be

        tol = 0
        for i = 1 to 8
        tol += i
        end for

        in scheme it'd be
        (define (sum a b)
        (if (equal? a b)
        b
        (+ a (sum (+ 1 a) b)))

        which is confusing. And not obvious. But as for other people's code, that is always the case. Well I've never seen a language that oculd get around that anyhow, the closest I think is java.

        • Re:Functionals (Score:2, Informative)

          by bigbadbob0 ( 726480 )
          Your scheme sum example runs fine for small summations. But for big numbers you'll blow the stack because you aren't tail recursive... a "better" solution to sum between a and b:

          (define (sum a b)

          (define (sum' mysum iter)

          (if (> iter b) mysum

          (sum' (+ mysum iter) (+ iter 1))
          )
          )
          (sum' 0 a) )

        • Re:Functionals (Score:3, Interesting)

          by Dasein ( 6110 ) *
          Ack! Using examples with side-effects to demonstrate functional programming! Sheesh. Try this on for size (from the About Haskell [haskell.org] page):

          Quicksort in Haskell

          qsort [] = []
          qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
          where
          elts_lt_x = [y | y <- xs, y < x]
          elts_greq_x = [y | y <- xs, y >= x]

          Quicksort in C

          qsort( a, lo, hi ) int a[], hi, lo;
          {
          int h, l, p, t;

          if (lo < hi) {
          l = lo;
          h = hi;
          p = a[hi];

          do {
          while ((l < h) && (a[

      • Re:Functionals (Score:3, Interesting)

        by QuantumFTL ( 197300 ) *
        I agree that functional programming languages are quite useful, 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.

        I'm not sure I'd consider most functional languages complicated. Look at the number of types and basic functions in something like SML or OCaml... a few basic types, and a few functions to act on them... There's really not a lot there to learn.

        If anything many functi
      • I think being a newbie to any type of programming makes understanding code that is not yours extremely difficult.

    • Re:Functionals (Score:2, Informative)

      by e4liberty ( 537089 )

      Having delivered commercial (yes!) applications on Lisp Machines, I can say with some authority that a G4 Mac with Digitool's Macintosh Common Lisp (MCL) is an excellent, probably superior substitute.

      The folks at Digitool [digitool.com], and Gary's OpenMCL [openmcl.org] is a nice free alternative if you don't need the GUI.

  • What is the world coming to? (Score:3, Funny)

    by TwistedSquare ( 650445 ) on Wednesday March 03, 2004 @01:11PM (#8453757) Homepage
    A while ago I read the comments following a Slashdot book review

    Next thing we know, people will start reading the books as well!

  • This was a great review (Score:5, Interesting)

    by jkauzlar ( 596349 ) * on Wednesday March 03, 2004 @01:12PM (#8453771) Homepage
    I've been learning OCaml on my own for the past several weeks and I've been wondering many of the things that this book seems to address, such as how the functional paradigm solves common problems differently than the imperative. I know first-class functions can significantly reduce the amount of code needed in many procedures...

    I guess what I'm saying is that I've used languages like Perl and Python considerably and ignored the functional aspects of the language, probably much to my disadvantage. I think a good study of a purely functional language could really improve my perl, python, or ruby.

    • Re:This was a great review (Score:5, Insightful)

      by SparafucileMan ( 544171 ) on Wednesday March 03, 2004 @01:19PM (#8453852)
      Actually perl has an alternate syntax that includes a functional language, and, of course, you can always write a functional language in perl. But most Perl code online (CPAN) isn't written like this, which pretty much defeats the purpose.

      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.

    • Re:This was a great review (Score:5, Interesting)

      by tcopeland ( 32225 ) * <{moc.dnalepoceelsamoht} {ta} {mot}> on Wednesday March 03, 2004 @01:20PM (#8453862) Homepage
      > I think a good study of a purely functional
      > language could really improve my perl,
      > python, or ruby.

      Right on. Here's a quote from Yukihiro Matsumoto, creator of Ruby [ruby-lang.org]:
      Learn more than one programming language, preferably many different styles, like scripting, object-oriented, functional, logic, etc.
      There's an Artima article [artima.com] where he gives some of his reasons for this idea. That whole series of interviews with him is pretty good.

    • XSLT (Score:3, Funny)

      by Black Perl ( 12686 )
      I think a good study of a purely functional language could really improve my perl, python, or ruby.

      A good study of the purely functional language XSL will really improve your appreciation of perl, python, or ruby!

  • eek! (Score:2, Funny)

    by happyfrogcow ( 708359 )

    article... triggering... college... flashbacks.


    ..must.. resist...


    ..cannot.. fight.. functional


    ..language.. tempatation...



    *head explodes*

  • The memories... (Score:5, Insightful)

    by kneecarrot ( 646291 ) on Wednesday March 03, 2004 @01:19PM (#8453853)
    I took a course back in university that used Scheme to teach some programming concepts. As with any course, we had to use Scheme to solve some problems on coding assignments. I remember a general rule everyone learned in the class: if your solution to the problem was more than a handful of lines, it was probably wrong. The solutions were very elegant, but very difficult to debug and very difficult to reason about.

    • Re:The memories... (Score:3, Interesting)

      by hc00jw ( 655349 )

      The solutions were very elegant, but very difficult to debug and very difficult to reason about.

      Just to clear up, this is because of the lazy evaluator. Because code is executed until it needs to be, you never know what's happening when. For example:
      System.out.println("I have reached this point");
      would be meaningless in a functional program, because from where was this code executed? Hence, not only have you got to re-learn how to write your programs, you have to re-learn how to debug them!

      (As a footnot

      • "I'd say the advantages (lazy evaluation, advanced pattern matching functions, less code, recursion, etc.) outweigh the disadvantages (hard to debug) by a mile!"

        Just out of interest, have you ever tried to solve any problems that were not inherently recursive (e.g. traversing a tree) using a functional language? Maybe I was just young and inexperienced but I really did find it to be a serious bitch!

        • Just out of interest, have you ever tried to solve any problems that were not inherently recursive (e.g. traversing a tree) using a functional language? Maybe I was just young and inexperienced but I really did find it to be a serious bitch!

          What is traversing a tree if not recursive? Here's what I do in OCaml:

          walk_dir [spy.net] to walk directory trees.

          I use that in an app that finds all files that meet certain criteria and performs an operation on them. It's a very straight-forward process. It also seems to b

      • Re:The memories... (Score:3, Insightful)

        by Jagasian ( 129329 )
        That is not true at all. Lazy evaluation is deterministic and sequential.

        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 retu

      • The solutions were very elegant, but very difficult to debug and very difficult to reason about.

        Just to clear up, this is because of the lazy evaluator. Because code is executed until it needs to be, you never know what's happening when.

        Except that Scheme is not lazy. The problem for the OP is probably in groking first order functions and closures. If you don't have your head wrapped around those two concepts, it's going to be difficult to see how even fairly simple programs work.

        For instance, in OO lang

    • Re:The memories... (Score:3, Interesting)

      by johnnyb ( 4816 )
      "The solutions were very elegant, but very difficult to debug and very difficult to reason about."

      If you get the right mindset, recursive solutions as employed in scheme are very easy to reason about and get correct. The reason is that you can use formal proofs to _prove_ the correctness of your code. You can use the mathematic principles of induction to prove that your code is correct, but only in a purely functional atmosphere.

      It takes a little getting used to if you are an imperative programmer, but
    • Functional programs are both easy to debug and easy to reason about due to properties such as strong static type safety, confluence, and referential transparency. These properties imply that you can reason about a program directly in the language of the program through the use of arbitrary evaluation.

    • Re:The memories... (Score:3, Insightful)

      by monadicIO ( 602882 )
      The solutions were very elegant, but very difficult to debug and very difficult to reason about.

      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 typechec

  • It's all in the constructors (Score:4, Informative)

    by skybrian ( 8681 ) on Wednesday March 03, 2004 @01:22PM (#8453889) Homepage
    Another way to think about functional programming is as constructor-based programming. Problems are solved by constructing lots of temporary objects that are a little closer to the solution, until you're finally in a position to construct the answer.

    You can do this in any language, but to be efficient, you need an good garbage collector and a compiler that can optimize out most of the temporary objects.

  • Just got this book (Score:5, Informative)

    by QuantumFTL ( 197300 ) * on Wednesday March 03, 2004 @01:26PM (#8453933)
    Nice review!

    I just got this book and it's clear the author has really done his research. His writing style is also very clear, concise and well thought out. Not overly chatty or pandering, yet not dryly accademic either. Precisely the kind of computer book I'd want to write!

    I'm glad the reviewer didn't try to talk a lot about why people should be interested in functional programs, however I must say that the ability to write large complex algorithms in very few lines, and prove mathematically that it works is simply a miracle in some situations. If you need to write a compiler (or do any other set of complex alogirthms on large recursive data structures, especially those that could take advantage of tagged unions, like Abstract Syntax Trees do) you should check out OCaml. And it doesn't hurt that it can figure out the type of all your functions and variables for you :)

    Oh, and if you happen to get this book, and want to play with OCaml, you can get the OCaml translation of the data structures in this book here [univie.ac.at].

    I dont' know if very many programmers will ever program in a purely functional language, however it seems that languages of the future will have to include things like first class functions and closures, as they are incredibly useful. I know Ruby and Python already support a lot of it.

    Oh and in case anyone's wondering, it *IS* possible to encapsulate things like notion of state, error handling, and I/O in a purely functional language ("side effect free" language) using something called monads [ed.ac.uk]. Now there's a fun concept to wrap your brain around!

    Hope some people here are brave enough to dig into a book like this that requires a bit of math, and more than a little faith at some points :)

    Cheers,
    Justin Wick

    • Re:Just got this book (Score:2, Interesting)

      by illustir ( 92508 )
      Oh and in case anyone's wondering, it *IS* possible to encapsulate things like notion of state, error handling, and I/O in a purely functional language ("side effect free" language) using something called monads. Now there's a fun concept to wrap your brain around!
      If someone can explain monads to me in an understandable fashion, I'll be eternally grateful.
      I tried to read that part of the tutorial a couple of times but I got my brain fused ever time.

      • Re:Just got this book (Score:5, Informative)

        by Jagasian ( 129329 ) on Wednesday March 03, 2004 @01:59PM (#8454307)
        Monadic programming is a fancy name for a pretty common sense design pattern used by functional programmers far before the theory of Monads was created. Basically you want a function that executes a list of commands, but the problem is that functions can only evaluate to pure values. So what you do is your function evaluates to a value that represents the list of commands you wanted to execute.

        So the design pattern consists of using functions that pass a state value in and out of each function, in addition to possibly other values. The pattern enforces some restrictions, one of which is: each state value can only be used once.

        So executing one command and then another involves each command being defined as a function that takes the world's state and returns the world's state after modification. Sequencing the two commands then consists of composing the functions such that the state is passed from one function to the next.

        There are additional properties required for something to be considered a Monad... and it turns out that this "design pattern" is a mathematical construct known from a branch of mathematics known as Category Theory, and that category theory construct is called a "Monad".

        A side note: category theory is basically the study of mathematical design patterns. Its more than that, but thats a good intuition for computer scientists to take when they study category theory.

        • Re:Just got this book (Score:5, Informative)

          by QuantumFTL ( 197300 ) * on Wednesday March 03, 2004 @02:08PM (#8454416)
          Monadic programming is a fancy name for a pretty common sense design pattern used by functional programmers far before the theory of Monads was created. Basically you want a function that executes a list of commands, but the problem is that functions can only evaluate to pure values. So what you do is your function evaluates to a value that represents the list of commands you wanted to execute.

          What makes them special is the mathematical rigor that *ensures* the properties you need from the monads, and greatly aids in proving properties of your algorithms. Things like associativty, and the left/right unit properties really help trivialize a lot of programming proofs.

          It's more than just a "fancy name", and I'd say the most exciting thing about it is that it allows the use of composition of monads to compose functionalities described inside them. It makes functional programs much more modular because of this, and allows one to add all kinds of features to something like an interpreter without hardly changing the signatures of any functions! Quite impressive compared to the normal craziness associated with refactoring a functional program.

          It's interesting to see how monads are used in Glassgow's Haskell compiler... much more useful than I ever though "some weird triple thing" from category theory could be.

          A side note: category theory is basically the study of mathematical design patterns. Its more than that, but thats a good intuition for computer scientists to take when they study category theory.

          I always thought Category Theory was best though of by CS students as a replacement for Set Theory that has a function-centric view... a more pure theory of functions (with applications to the lamda calculus no less) that can usefully find common structure in many disparate fields of mathematics, especially discrete math.

          Cheers,
          Justin Wick

      • Monads are trivial. (Score:3, Informative)

        by Kickasso ( 210195 )
        Really. Try this one: http://www.nomaware.com/monads/html/index.html
  • I wrote a Sieve of Erasthones program in Haskell yesterday, and although it's amazingly short, and easy to understand (after you get your head around infinite lazy lists ;-), it's also terribly inefficient (big O-wise, it seems), at least compared to a version I wrote in C. I think it would run faster if I let the garbage collector use more memory, but I haven't looked into that.

    So, functional programmers, how to improve such a program without simply mimicking the imperative version?

    import System
    import

    • This [cryp.to] one. It runs pretty fast, though it can take quite a while to compile...
    • I was taught functional programming by a rather camp lecturer, who spoke with a lisp (no pun intended), and I could never keep a straight face whenever he said 'bottom'. Nor when he pronounced 'sqrt' as 'squirt'.

      He once defined a function called 'my', and then proceeded to use the unfortunate expression "squirt my bottom".

      Now, whenever I see Haskell, I see it as being just riddled with sexual innuendo that I can't get out of my head.....

      > minus x = x - 1
      > lubricated x = x == 0
      > harder x y =

  • I bought this book (Score:5, Informative)

    by johnnyb ( 4816 ) <jonathan@bartlettpublishing.com> on Wednesday March 03, 2004 @01:33PM (#8454006) Homepage
    I bought this book about 6 months ago. I *love* it. The author did an excellent job showing many interesting algorithms. I did have to read it a few times to make sense of it, as I am not as engaged in the functional programming community as I would like. I still have trouble figuring out how to apply the banker's method and the physicist's method when determining the amortized performance of functional algorithms.

    Anyway, the book was a great read. I was really surprised to learn how efficient some of the functional data structures could be.

    Good discussion as well on the use of suspensions (lazy evaluation for specific blocks of code) in programming.

  • Online version available (Score:5, Informative)

    by johnnyb ( 4816 ) <jonathan@bartlettpublishing.com> on Wednesday March 03, 2004 @01:39PM (#8454073) Homepage
    Also, since this was this guy's thesis, it's also available online

    See http://www-2.cs.cmu.edu/~rwh/theses/okasaki.pdf [cmu.edu].

    I suggest you get the book, however, as it's a great read.

  • Another Book ... (Score:2, Informative)

    by Anonymous Coward
    "A while ago I read the comments following a Slashdot book review. Someone had posted a request for books that covered a wider range of languages than..."

    Well he why not try "Comparative Programming Languages" it covers most of them.

    Here is an excerpt:

    "This book considers the principal programming language concepts and how they are dealt with in object-oriented languages such as Java and Delphi, in traditional procedural languages such as Pascal, C and Fortran, in hybrid object-oriented or object-based l
  • These agile/functional languages are great. And noteworthy, non-trivial systems have been written in them. The best part is that they can almost all be used inside of other apps as the "scripting" language. In one of our apps, users could use ECMA Script or Python (actually Jython). We eventually dropped Python because no one used it and the the next generation of our tool dropped ECMA Script because it was not considered mainstream (regardless of many lines web developers are writing and browsers execu
    • If you look here [microsoft.com], you will notice that our friends at Microsoft have developed a high level decompiler for .Net IL. Basically, it decompiles the IL into an abstract, non binary, human readable form.

      The tool for manipulating this new IL (ILX) is F#, an ML family functional language. This is because ILX fits more naturally with a functional language than it would with, say, C# or C++.

      C# and the like can still be used, but if you look at the ILX and compare it to F#, the reason for using a functionl lang

  • Scala (Score:3, Informative)

    by Channing ( 514228 ) <channingwalton@@@mac...com> on Wednesday March 03, 2004 @01:41PM (#8454095) Homepage
    Have a look at Scala [scala.epfl.ch] if you are looking for a language that supports both paradigms.

    From their site:

    Scala is a pure object-oriented language in the sense that every value is an object. Types and behavior of objects are described by classes and traits. Class abstractions are extended by subclassing and a flexible mixin-based composition mechanism as a clean replacement for multiple inheritance.

    Scala is also a functional language in the sense that every function is a value. Scala provides a lightweight syntax for defining anonymous functions, it supports higher-order functions, it allows functions to be nested, and supports currying. Scala's case classes and its built-in support for pattern matching model algebraic types used in many functional programming languages.

  • But what data structures? (Score:5, Informative)

    by QuantumFTL ( 197300 ) * on Wednesday March 03, 2004 @01:43PM (#8454112)
    This review was awesome, but he didn't really mention what data structures are discussed. Here's the list from the TOC for those who care:

    Heaps:
    • Leftist
    • Binomial
    • Splay
    • Pairing
    • Skew Binomial
    • Lazy Pairing

    Trees:
    • Binary Search
    • Red-Black
    • Trie

    Queues:
    • FIFO
    • Banker's
    • Physicist's
    • Double Ended


    There's also a lot of other things, such as some interesting ways of doing numerical representation in functional languages (lazy numbers!) Even talks about trinary/quaternary numbers, as discussed before on slashdot.

    Also if you'd like to see the source code without buying the book (you cheap bastard!) you can find it here [wu-wien.ac.at].

    But I hope you buy the book :)

    Cheers,
    Justin

  • A coder's hobby (Score:3, Insightful)

    by Bohnanza ( 523456 ) on Wednesday March 03, 2004 @01:44PM (#8454126)
    I (a software engineer paid to work with Java, C, Python, etc) choose to use in my spare time, just for the joy of coding.

    So this is what computer programmers do in their spare time - program computers! WooHoo!

    • Re:A coder's hobby (Score:3, Interesting)

      by RPoet ( 20693 )
      Yeah, can you imagine working with something you enjoy that much? It's preposterous.

    • Re:A coder's hobby (Score:3, Insightful)

      by jejones ( 115979 )
      So this is what computer programmers do in their spare time - program computers! WooHoo!

      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
  • ...that you can design data structures that parallel the way in which you represent numbers? You mean like this [mac.com]?

  • Functional Programming missed the boat (Score:5, Interesting)

    by Ars-Fartsica ( 166957 ) on Wednesday March 03, 2004 @01:52PM (#8454224)
    I was weaned in college on Haskell, and I love it still, but the bottom line is that the programming language industry is a fashion industry. Functional languages are lacking a big corporate/open source backer to glamorize and promote their goodness. Java is a perfect example of how you can hawk a programming language to saturation regardless of its relative merits.

    Network effects are what rules the programming tools industry. Network effects are whim to fashion. Fashion is ruled by those with the legitimacy to glamorize.

    • For algorithms that are sequential, only make use of heirarchical data structures, and are not very interactive, functional programming is typically a good choice.

      However, if your algorithm involves allot of interaction, multiple threads of execution, or anarchical data structures (e.g. cyclic structures)... then functional programming isn't the best tool for the job.

      Another note, if there is no good algorithm for your problem, that is, it basically involves brute force searching of some sort... then cons

    • Re:Functional Programming missed the boat (Score:5, Insightful)

      by The Pim ( 140414 ) on Wednesday March 03, 2004 @02:37PM (#8454734)
      If you examine these "fashions", you'll see many examples of Philip Greenspun's adage that "The exciting thing in computer science is always whatever we tried 20 years ago and didn't work" [greenspun.com]. Industry is ever rediscovering and popularizing old ideas from academia. Even Java, while primitive, took some of its main selling points (garbage collection, portable bytecode) from the ivory tower. In Paul Graham's words, "the default language, embodied in a succession of popular languages, has gradually evolved toward Lisp" [paulgraham.com]. These are different ways of saying that if the ideas are good (and good ideas abound in the functional programming community), the mainstream will pick them up eventually.

      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.

    • I don't think that's necessarily the case. Java and other languages have become popular because it is relatively simple to understand and can do things that are expected of real-world programs, like graphics. How many OpenGL interpretations done entirely in Scheme can you count? What about basic Windows applications?

      Furthermore, I think it's also the result of software firms wanting to segment many areas of a program into smaller compartments. OOP makes this easier by enforce abstract and interface ty

  • Hard to use in the "real world". (Score:5, Informative)

    by Godeke ( 32895 ) * on Wednesday March 03, 2004 @02:56PM (#8455037)
    I love functional programming. If I had my way, my projects would all use functional programming languages. I don't have my way however, and there are two reasons.

    1. Few commercial tools: Functional languages are under represented in the commercial space. With the exception of Franz Lisp and a few other lisp dialects, there is little commercial support. That may not be a killer for everyone, but I would like an environment with a good form designer and a large library to back me up. One I could give to another coder and expect them to be productive with it. Emacs works as an IDE for me, but I can't force that on others...

    2. Fewer programmers: The vast majority of programmers seem unable/unwilling/whatever to grasp the concepts and work with functional code. If you need to build a team of programmers, it is much harder to find those who can do functional programming (and when you do, they rock, but are expensive and in high demand).

    In the end, I use commonly used commercial tools so I can work with other people. Internally I use a lot of non commercial tools (LAMP model) and so I can sometimes indulge in my functional side there, but rarely can I do functional programming for my business clients.

  • Took Okasaki's data structures course (Score:5, Interesting)

    by philgross ( 23409 ) on Wednesday March 03, 2004 @02:59PM (#8455079) Homepage
    Here's a reason to get a Computer Science degree at a good school: you can take a course on data structures taught by Chris Okasaki, the book's author. I took Advanced Data Structures from him at Columbia in 1999. Now he's at West Point [usma.edu].


    The course was pretty mind-blowing. He knows his stuff. It was a bit freaky to watch him grading programming assignments by just reading them, not running them, and yet never missing a mistake.


    I would recommend the book not just as an introduction to advanced data structures in functional languages, but as a guide to some of the more interesting data structures of the last fifteen years, regardless of implementation language.


    -- Phil Gross

  • The tyranny of momentum: why Ocaml is not popular (Score:5, Informative)

    by zeno_lee ( 125322 ) on Wednesday March 03, 2004 @03:05PM (#8455152)
    Programming in a functional language allows you to be more concise and expressive. Some studies indicate that development time is 4 times shorter, and the resulting code is 4 times smaller and is much easier to read.

    Take a language like Ocaml.

    It is a functional language with imperative features (loops, mutable data structures), modular organization, has object orientation, compiles to portable byte code (like Java and the JVM) as well as compiling to native code that runs as fast as C, has garbage collection, and a good standard library.

    I'm thinking the reason why there are such few people picking up functional programming is the same reason the US still uses the imperial system for measurement.

    While the rest of the world is on the metric system, the U.S. still uses the strange imperial system, that uses things like 12 inches to a foot, 3 feet to a yard, 16 ounces to a pound. That's because the US is entrenched in a mindset and there's no driving reason to change. This is the same reason why people have been stuck on imperative languages. Imperative languages have been the overriding paradigm because in the past, processing time and memory were expensive and imperative languages. This is no longer the case but there is a huge momentum of imperative language that that rolls on like a giant snowball, reinforced by industry and entrenched upon the next generation of computer programmers.

    How did I discover Ocaml?

    I was investigating rapid prototyping languages to add to my toolbelt and ran across Ocaml. I was drawn to it because it has done extremely well in the ICFP contests, especially in the lightning division (24 hour submission).

    Also it ranks impressively in the great language shootout by Doug Bagley, in terms of Lines of Code, Execution Speed, and memory consumption.

    http://www.bagley.org/~doug/shootout/

  • Letting you in on a little secret (Score:4, Interesting)

    by GodSpiral ( 167039 ) on Wednesday March 03, 2004 @03:10PM (#8455218)
    OOP SUCKS!

    Encapsulation is a restriction not a benefit.
    Just as non-open source software allows your data to be held hostage by the class producer authors.
    Reusability is poor because while both Accounting and Genealogy software might use a person object neither is interested in holding the other's baggage.
    An object hierarchy becomes a house of cards, built on excruciating desicions of what to include and exclude at each level, and how much baggage to bring along.
    Really the only good that ever came out of OOP was a straightforward way of passing around references to the same data, and easily creating and destroying records from classes.

    <a href="http://www.lua.org/home.html">Lua</a&g t; is probably the best syntactically designed language out there in terms of both expressive power and readability.

    It has an easy to read vb/pascal like syntax without semicolons.
    It has full functional powers
    No silly restrictions such as immutable variables.
    Tables as a replacement to both lists, and classes,
    essentially fully associative keyed lists
    and since any value can be a function a Table can act as a "method" container.
    Powerful extention mechanisms to define class inheritance/relationships within the language itself (rather than the compiler).
    great calling convention with multiple assignment/return values.

    Lua is a great introductory language, in that it is exceptionally readable. While you will immidiately gravitate to using functional paradigms, you're not forced to using them exclusively. It has elegant OOP and imperative paradigms as well.

  • Good book? Yes. Useful? Not really. (Score:3, Interesting)

    by Junks Jerzey ( 54586 ) on Wednesday March 03, 2004 @03:27PM (#8455394)
    The majority of this book is devoted to esoteric data structures. Sure, it starts with queues and stacks, but most of the book is devoted to exotic forms of trees and tries and heaps and so on. Very interesting stuff. In reality, though, you get by with a small subset of data structures: arrays and lists (both of which can be thought of as stacks or queues), binary trees, and hash tables / dictionaries. Almost always, once you start delving into crazy forms of trees, you can jump straight to a hash table and be done with it. Purely Functional Data structures is very light on information about hashing.

    I'm speaking from experience as both a functional and imperative programmer. While I have enjoyed the book, I didn't find it to be something that I keep returning to over the years.

  • Prefer databases (Score:3, Interesting)

    by Tablizer ( 95088 ) on Wednesday March 03, 2004 @03:34PM (#8455490) Journal
    Over the years I have grown more fond of databases over "data structures". I know this will probably start a holy war, but at least let me express my viewpoint.

    Relational tables are more stable as requirements change. Relational tables are mostly designed around the quantity of relationships between things, such as one-to-many, many-to-many, etc. They are NOT dictated by how they are actually used in a given application for the most part. This at first sounds bad, but it is good because normalized tables transcend specific uses, and are thus more flexible and change-friendly. Relational tables are to describe nouns and facts about nouns, not reflect specific tasks or usages. Thus, you don't end up with "pointer messes".

    For example, if you want to represent a graph with dedicated data structures, you might be tempted to make a list of lists, where one list is the ID's (or pointers) to other nodes (links). But if one is later required to put weights on these links, then a list is no longer appropriate, and you have to overhaul your structures and code that references them. However, a (properly normalized) relational database would use a many-to-many table to represent the links. Adding a weight factor is a trivial column addition. Existing code still works without change (as long as it does not reference or need weight info of course).

    However, SQL and tradition has "bulked up" databases beyond what they need to be for many applications. A light-duty "local" relational engine to complement or replace "big-iron" RDBMS would be nice. I used to use "nimble table engines", and they were easy-to-use and relatively quick. SQL is not the ideal relational language, especially for smaller DB engines. I would like to see the industry explore alternative relational languages. Then we could get away from the pressure to use dedicated data structures. I find them archaic, to be frank. Let's move on.

  • I have implemented some of these in Ocaml (Score:4, Interesting)

    by j h woodyatt ( 13108 ) <jhw@conjury.org> on Wednesday March 03, 2004 @03:35PM (#8455509) Homepage Journal
    If you're interested in Objective Caml, I have implemented [inria.fr] some of the data structures mentioned in this book, i.e. just the ones I wanted the most.

    Red-black binary tree

    Skew-binomial heap

    Real-time catenable deque

    They're buried in a library containing a lot of other goodies that I haven't ported to all the platforms where Ocaml runs. The data structure modules are pure Ocaml, though- so, you can just lift them. The library is BSD licensed (two-clause), so take all the liberties you want as long as you give me props in your distribution and you can cope with the fact that you get NO WARRANTY from me. (It would be nice if you told me you were using it too-- that would help motivate me to care about timely release of updates.)

    * The real-time deque is not technically a pure functional data structure since it uses lazy evaluation for handling concatenation, but- to be fair, a lot of the algorithms in Okasaki's book have a similar property. He is, of course, careful to distinguish the difference between pure and non-pure functional data structures.

  • Let me also try to explain why FP is good (Score:4, Informative)

    by Tom7 ( 102298 ) on Wednesday March 03, 2004 @04:51PM (#8456468) Homepage Journal
    Regarding write-once variables: the reviewer makes it sounds as though this is some terrible burden or restriction that functional programmers must deal with. I offer the contrary point: immutable structures are an *invariant* that make programming much, much easier. Have you ever been in a situation where some other part of the code has an alias to something you're working with, and is modifying it when you don't want it to? Functional programming totally avoids that by having a language-enforced invariant of immutability.

    That (along with all of the other features that functional languages typically have that languages like Java and C don't, like higher order nested lexically-scoped functions, polymorphism, algebraic data types and pattern matching, parameterized modules, tuple and sum types, etc.) is the reason to do functional programming. Of course, SML and O'Caml allow you to program imperatively too, since some activities are more naturally expressed that way.

    I used to be a total C cowboy, and now I love functional programming. You can just do so much more great stuff with it.

    IMO, mlton [mlton.org] is a great compiler with which to start functional (SML) programming. The performance is incredibly good, it behaves like a real compiler from the command line, and it's free (GPL) software.

Slashdot Top Deals

Do you suffer painful illumination? -- Isaac Newton, "Optics"

Close