Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Purely Functional Data Structures

timothy posted more than 10 years ago | from the raw-function-baby dept.

Programming 427

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.

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.

cancel ×

427 comments

Hola! (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#8453642)

The penis: mightier than the sword!

FUCK (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#8453656)

in ass
NAZI

fffffff----f-----fffff---fffff--fffff ff-fffffff
f---------f-f---f-----f-f-----f-f----- f----f
f--------f---f--f-------f-------f-----f--- -f
fffff---f-----f-f--ffff-f--ffff-f-----f----f
f-------fffffff-f-----f-f-----f-f-----f----f
f--- ----f-----f-f-----f-f-----f-f-----f----f
f------- f-----f--fffff---fffff--fffffff----f

# Important Stuff: Please try to keep posts on topic.
# Try to reply to other people's comments instead of starting new threads.
# Read other people's messages before posting your own to avoid simply duplicating what has already been said.
# Use a clear subject that describes what your message is about.
# Offtopic, Inflammatory, Inappropriate, Illegal, or Offensive comments might be moderated. (You can read everything, even moderated posts, by adjusting your threshold on the User Preferences Page)

Eurotrash (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#8453659)

I hate Eurotrash. Europe sucks and their leaders mean nothing.

Re:Eurotrash (0, Funny)

Anonymous Coward | more than 10 years ago | (#8453685)

Good thing they left 300 yers ago then.

do it (-1, Troll)

Anonymous Coward | more than 10 years ago | (#8453675)

in the butt

Fourth Post (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#8453681)

Fourth post! Pwnage!

Re:Fourth Post (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#8453699)

you failed miserably as 5th.. lamer

Re:Fourth Post (-1, Troll)

Anonymous Coward | more than 10 years ago | (#8453815)


  1. Face it, you are my bitch. Bow down and feel the power of the almighty java cock. That is the dot on your fucking head up there APU

Purely *Functional* Data Structures (4, Funny)

Orne (144925) | more than 10 years ago | (#8453687)

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

Re:Purely *Functional* Data Structures (-1, Troll)

generationxyu (630468) | more than 10 years ago | (#8453735)

RTFA, and learn SOMETHING about programming.

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

MooseByte (751829) | more than 10 years ago | (#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.)

Re:Purely *Functional* Data Structures (2, Funny)

Michael Iatrou (681428) | more than 10 years ago | (#8453788)

Have you tried Microsoft Press?

Re:Purely *Functional* Data Structures (-1, Troll)

AKAImBatman (238306) | more than 10 years ago | (#8453850)

Of course, some readers won't know what functional programming is, or what is special about pure data structures.

Truly sad. I never got a Comp-Sci degree myself, and I know more about procedural, functional and OO data structures than pretty much every comp-sci student I've met. What are they teaching kids these days!? Oh, that's right. Teachers are teaching only what you need to get a job, and students are hacking code they don't understand instead of learning.

Disgusting.

Re:Purely *Functional* Data Structures (5, Insightful)

I_Love_Pocky! (751171) | more than 10 years ago | (#8454069)

I never got a Comp-Sci degree myself

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.

Over where I work (5, Funny)

Anonymous Coward | more than 10 years ago | (#8453693)

Management prefers dysfunctional programming.

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

laurent420 (711504) | more than 10 years ago | (#8453697)

blonde... brunette..

Uh hello, Matrix quote? (1)

Ayanami Rei (621112) | more than 10 years ago | (#8454191)

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! (5, Informative)

jaaron (551839) | more than 10 years ago | (#8453700)

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.

Re:Nice Review! (1, Insightful)

jdavidb (449077) | more than 10 years ago | (#8453955)

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.

O'Camel (4, Interesting)

Robert Webb (172183) | more than 10 years ago | (#8453709)

Is 'OCaml' pronounced 'Oh-Camel', 'Ach-amel'...? Akin to the 'Line-Ux' versus 'Lin-Ux' confusion.

Re:O'Camel (3, Informative)

Anonymous Coward | more than 10 years ago | (#8453801)

You read it like OKamell with a french accent (its developers are french).

Re:O'Camel (0, Flamebait)

colmore (56499) | more than 10 years ago | (#8454012)

So what then, the compiler is strict and rude about it? It won't adapt to admit even comonly used keywords from other, more popular languages?

Re:O'Camel (1)

smitty_one_each (243267) | more than 10 years ago | (#8454023)

But when you say 'OK-mull', the actual sound is rather Australian, Bruce.

Re:O'Camel (0)

Anonymous Coward | more than 10 years ago | (#8454049)

Akin to the 'Line-Ux' versus 'Lin-Ux'

Where do you see an "e" in "Linux"?

As for "OCaml", if people would boycott things that have names that they can't pronounce, these products would die quiclky and we'd only be left with names that we can pronounce.

Data Structures (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#8453710)

Data Structures suck on windows when used by SCO and the RIAA and the Republicans. Mac rules, linux rules! I have no penis!

Re:Data Structures (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#8453740)

Its ON TOPIC YOU MINDLESS MOD FUCKS its about data structures. Mod me up apu

Re:Data Structures (-1, Troll)

Anonymous Coward | more than 10 years ago | (#8453787)

What the fuck is wrong with you mods? Are you on the Steve Jobs Cockboat or what? Mod me the fuck up!

Re:Data Structures (-1)

Anonymous Coward | more than 10 years ago | (#8453877)


  1. I can't believe you lamers. Is archangel modding or something? What the hell is going on. Java isn't going open source, no one cares about SCO or linux, everyone runs windows, only the US matters, and evoting sucks. give it up you dorks.

Misread Headline (2, Funny)

glarvat (753298) | more than 10 years ago | (#8453713)

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 (5, Funny)

JoshuaDFranklin (147726) | more than 10 years ago | (#8453714)

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

Re:Not a typewriter (5, Funny)

ornil (33732) | more than 10 years ago | (#8453953)

He did, but because of lazy evaluation it ended up after the second part.

Re:Not a typewriter (1)

GoofyBoy (44399) | more than 10 years ago | (#8453973)

3x4c+ly. i h4vE no id3A why pEopl3 S+ay WI+H oU+-OF-D4T3 c0nVenT10n$.

But, like... (1)

Short Circuit (52384) | more than 10 years ago | (#8454096)

But people like it.

Typing like you talk--well, if you talk flowingly--typing how you talk makes (people hate this about me) it makes it more conversational.

Re:But, like... (1)

GoofyBoy (44399) | more than 10 years ago | (#8454142)

Previous message = False.

( Short + accurate ) + communiction = good.

Computer != typewriter.

End of message.

WTF?! (-1, Offtopic)

Neophytus (642863) | more than 10 years ago | (#8453717)

i read this yesterday? was this a story that was posted to subscribers then pulled before publication?

I like any language (5, Funny)

donnyspi (701349) | more than 10 years ago | (#8453734)

that supports GOTOs. Those are the best!

Re:I like any language (3, Informative)

Waffle Iron (339739) | more than 10 years ago | (#8453793)

that supports GOTOs. Those are the best!

Well, the functional language Scheme supports "continuations". These are kind of like GOTOs on acid.

Re:I like any language (-1)

Anonymous Coward | more than 10 years ago | (#8454046)

you mean like call-with-current-continuation? that's not like goto at all huh

Re:I like any language (-1)

Anonymous Coward | more than 10 years ago | (#8453823)

that ok, i wont use a language that doesnt have them.

that, and direct memory access.

Re:I like any language (0)

Anonymous Coward | more than 10 years ago | (#8453894)

When told, "goto hell", a programmer finds the method, not the destination as harmful.

Re:I like any language (0)

Anonymous Coward | more than 10 years ago | (#8453946)

What is this GOTO you speak of?

Re:I like any language (-1)

Anonymous Coward | more than 10 years ago | (#8454059)

It's like a jump or branch instruction you might find in assembly language.

GOTO is good, but ... (0)

Anonymous Coward | more than 10 years ago | (#8454037)

... I prefer COME_FROM.

Re:I like any language (1)

Christopher H (25358) | more than 10 years ago | (#8454194)

The joke is on you: tail recursion can be seen as the ultimate evolution of GOTO.

The tail-recursive factorial function in Scheme or ML is completely equivalent to an iterative one with goto, except that it's safer and clearer.

In most functional programming languages you can code (for instance) state machine transitions directly by 'calling' the next state. Since the call is in tail position, it acts almost exactly like GOTO.

(I won't even mention typed assembly languages like TALx86 or the continuation semantics of your CPU...)

i dont get it (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#8453738)

what does this have to do with SCO?

fri57 stop... (-1, Troll)

Anonymous Coward | more than 10 years ago | (#8453752)

Functionals (3, Interesting)

SparafucileMan (544171) | more than 10 years ago | (#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 (0)

Anonymous Coward | more than 10 years ago | (#8453821)

You go first, we'll catch up.

Re:Functionals (4, Interesting)

ill_mango (686617) | more than 10 years ago | (#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 (4, Informative)

SparafucileMan (544171) | more than 10 years ago | (#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 (5, Insightful)

Kupek (75469) | more than 10 years ago | (#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 (3, Interesting)

Arcanix (140337) | more than 10 years ago | (#8454047)

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 comfortable with the most although you can obviously learn others. In coding its a bit more complex since you may find that your first language was terrible and pick up another one but people will generally stay in the same paradigm of imperative, functional or OO. It is a challenge to cross over once your mind works in a certain way.

Re:Functionals (0)

Anonymous Coward | more than 10 years ago | (#8454114)

i doubt it. a decent lisp programmer would simply implement lisp in c, then go for it. all you really need are linked lists, and a symbol table.

Re:Functionals (2)

hc00jw (655349) | more than 10 years ago | (#8454053)

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 is due to it's strong typing of course). Sure, there are still certain concepts to understand with functional programs that aids your reading of other peoples code... But then, that's the same with programming in general anyway!

Re:Functionals (4, Insightful)

Temporal (96070) | more than 10 years ago | (#8454141)

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 (5, Insightful)

Anonymous Coward | more than 10 years ago | (#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?

Re:Functionals (1)

nosferatu-man (13652) | more than 10 years ago | (#8454177)

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" approach. I may be speaking as too much of a logic geek here, but wouldn't that in all cases be simpler?

'jfb

Re:Functionals (5, Informative)

gangien (151940) | more than 10 years ago | (#8454197)

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 (2, Informative)

e4liberty (537089) | more than 10 years ago | (#8453952)

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? (3, Funny)

TwistedSquare (650445) | more than 10 years ago | (#8453757)

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 (5, Interesting)

jkauzlar (596349) | more than 10 years ago | (#8453771)

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 (5, Insightful)

SparafucileMan (544171) | more than 10 years ago | (#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 (3, Informative)

SparafucileMan (544171) | more than 10 years ago | (#8454021)

I should have included this link:

Perl Contains the Lambda Calculus [plover.com] .

Working with the Lambda Calculus on a computer, as a mathematician who is used to only the brain and pen/paper, makes me alternatively want to piss my pants and orgasm everywhere. It's, like, the simplest programming language on the earth!

Re:This was a great review (1)

rmull (26174) | more than 10 years ago | (#8454168)

Grrrr... as much as I WANT to get fired... Don't follow the link! Grrr.

Re:This was a great review (4, Interesting)

tcopeland (32225) | more than 10 years ago | (#8453862)

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

Re:This was a great review (0)

Anonymous Coward | more than 10 years ago | (#8453879)

Functional programming is mostly useful when you deal with inductive types and data structures, like those used in compilers. The paradigm is less useful when you're programming numerical stuff. Difficult to hack, too.

eek! (2, Funny)

happyfrogcow (708359) | more than 10 years ago | (#8453780)

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


..must.. resist...


..cannot.. fight.. functional


..language.. tempatation...



*head explodes*

Re:eek! (0)

Jackmon (170028) | more than 10 years ago | (#8454018)

Parentheses!!! Swarms of parentheses!!! Oh God!! NOoooooo!!!! AAAAaaaaarrrggghhhh!!!

The memories... (4, Insightful)

kneecarrot (646291) | more than 10 years ago | (#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... (3, Interesting)

hc00jw (655349) | more than 10 years ago | (#8453962)

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 footnote, I'd say the advantages (lazy evaluation, advanced pattern matching functions, less code, recursion, etc.) outweigh the disadvantages (hard to debug) by a mile!)

Re:The memories... (1)

kneecarrot (646291) | more than 10 years ago | (#8454090)

"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!

Re:The memories... (2, Insightful)

Jagasian (129329) | more than 10 years ago | (#8454125)

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

Re:The memories... (2, Interesting)

johnnyb (4816) | more than 10 years ago | (#8454043)

"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 its worthwhile.

However, I will say that the indentation practices of most Schemers is dreadful, and is one of the reasons why tab characters should not be directly equivalent with 8 characters. You see, if you make a tab equivalent to "arbitrary indentation of one level", then the user can set their own tab stops, and when a statement gets unwieldly and deep, you can just shorten the indentation to 1 or two spaces. But when you need some whitespace to view the algorithm better, you can expand it to 4
or 5, or even 8.

Re:The memories... (1)

Jagasian (129329) | more than 10 years ago | (#8454154)

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... (2, Insightful)

monadicIO (602882) | more than 10 years ago | (#8454155)

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 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).

Translation of Okasaki's sources from SML to OCAML (2, Informative)

bcolflesh (710514) | more than 10 years ago | (#8453868)

4.1.8. PureFun [univie.ac.at]

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

skybrian (8681) | more than 10 years ago | (#8453889)

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.

Re:It's all in the constructors (1)

jaaron (551839) | more than 10 years ago | (#8453992)

"Constructor-based Programming" is approximately the same as Dependency Injection [martinfowler.com] which is related to Inversion of Control which means if you program in Java, you should look at Apache Avalon [apache.org] , PicoContainer [picocontainer.org] , and/or the Spring Framework [springframework.org] . Enjoy!

Just got this book (4, Informative)

QuantumFTL (197300) | more than 10 years ago | (#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 (1)

Sparky77 (633674) | more than 10 years ago | (#8453967)

Wow, that was fast! Are you browsing Slashdot from the bookstore?

Re:Just got this book (3, Interesting)

QuantumFTL (197300) | more than 10 years ago | (#8454162)

Wow, that was fast! Are you browsing Slashdot from the bookstore?

No no no... I just got the book a few days ago and have been reading it. I've forced myself to play around with OCaml and various functional languages for the last month or so to try out the paradigm, and I must say I'm impressed by the compact expressivity, and the safety of these languages.

I love the idea of writing programs that can't crash (well, they can hang but they can't segfault), and being able to so elegantly describe an algorithm that I might as well just be writing the math.

I'm also not exactly upset by the type-inference (I never have to specify the type of almost *ANYTHING* despite the fact that there's no implicit casting). Also being able to make functions that are polymorphic in extremely complex ways allows me to keep algorithms much more general. Functors, for those that havne't used them, are simply awesome. Think templates but done right.

We need more good book reviews like this. Slashdot should hire the guy :)

Cheers,
Justin Wick

Re:Just got this book (2, Interesting)

illustir (92508) | more than 10 years ago | (#8454050)

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 (-1)

Anonymous Coward | more than 10 years ago | (#8454101)

(where(are)(the(obligatory(lisp)(syntax))(jokes))) ?

functional algorithms (1)

sir99 (517110) | more than 10 years ago | (#8453970)

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 Numeric

x `divides` y = y `rem` x == 0

sieve :: [Int] -> [Int]
sieve (x:xs) = x : sieve [y | y <- xs, not (x `divides` y)]

primes = 2: sieve [3,5..]
-- sieve [2..] would also work

main = do args <- getArgs
let count = fst (head (readDec (head args))) in
putStr ((show (take count primes)) ++ "\n")
Slashdot ate my spaces.

Re:functional algorithms (1)

SparafucileMan (544171) | more than 10 years ago | (#8454063)

Shoulda written it in LISP, no one knows Haskell. ;)

As far as big-O goes, all you need to know is that somewhere is a C implementation of the recent proof that PRIME (aka, finding all the primes) is not greater than n (aka, linear). It might be log something, but I forget and am lazy.

Re:functional algorithms (1)

sir99 (517110) | more than 10 years ago | (#8454212)

Actually, I adapted the Haskell code from someone's thesis [216.239.41.104] about stream (i.e. lazy list) algorithms, in Scheme.
(define (sieve stream)
(cons-stream
(stream-car stream)
(sieve (stream-filter
(lambda (x)
(not (divisible? x (stream-car stream))))
(stream-cdr stream)))))

(define (integers-starting-from n)
(cons-stream n (integers-starting-from (+ n 1))))

(define primes (sieve (integers-starting-from 2)))

I bought this book (4, Informative)

johnnyb (4816) | more than 10 years ago | (#8454006)

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.

Anyone else reminded of Star Trek? (-1)

Anonymous Coward | more than 10 years ago | (#8454007)

Data's structure was fully functional, too. Just ask Tasha.

Re:Anyone else reminded of Star Trek? (-1)

Anonymous Coward | more than 10 years ago | (#8454106)

Yar!!

I heard this mentioned on some previous article (1)

emurphy42 (631808) | more than 10 years ago | (#8454057)

Microsoft Excel is a functional programming language. Discuss.

Online version available (5, Informative)

johnnyb (4816) | more than 10 years ago | (#8454073)

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 ... (2, Informative)

Anonymous Coward | more than 10 years ago | (#8454087)

"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 languages such as C++ and Ada 95, in functional languages such as ML and in logic languages like Prolog. "

There is also a link to it:

http://www.cs.stir.ac.uk/~rgc/cpl/

which I post as plain text because I'm lazy right now and also because I hope this prevents compulsive clickers (are there such people?) from going there without getting too much wisdom out of it. There is after all this much feared slashdot effect.

Have fun

Cool languages, but why... (2, Interesting)

chamilto0516 (675640) | more than 10 years ago | (#8454092)

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 executing at this very moment) and we took hits for that. The current generation of that tool uses Java only.

I enjoy learning new programming languages but because of stuff like this, I wonder why I should. I still will because I have done non-trivial stuff in them very easily but it is a big downer. At least they let authors write neat books for us geeks to take on vacation.

Scala (3, Informative)

Channing (514228) | more than 10 years ago | (#8454095)

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.

Laziness Bad (1)

firewrought (36952) | more than 10 years ago | (#8454097)

The good side is that laziness can help make programs more efficient.

My understanding was that, in general, the "efficency" of laziness is outweighed by the cost of the bookkeeping for it. After all, a function uses the parameters it is passed most of the time.

I'm a fan of functional programming, but lazy evaluation complicates the code and slows it down. That's one advantage of scheme's function-calling semantics over lisp's, IIRC (can anyone confirm?).

Lisp (1)

venomix (87217) | more than 10 years ago | (#8454102)

I'm learning lisp at the univeristy right now, it's really another world, upside down and inside out, for me who's used to c/c++ =)

But what data structures? (4, Informative)

QuantumFTL (197300) | more than 10 years ago | (#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

Functional use (0, Flamebait)

Tenebrous (119888) | more than 10 years ago | (#8454113)

"But I'm getting ahead of myself, because I haven't described what a functional language is, or why it is useful"

I seached monster dot com for lisp and got 12 hits, so clearly there's a use for it.

A coder's hobby (2, Insightful)

Bohnanza (523456) | more than 10 years ago | (#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!

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...