Purely Functional Data Structures

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.

Comments

Re:Eurotrash

[Anonymous Coward]

Good thing they left 300 yers ago then.

Purely *Functional* Data Structures

[Orne]

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

Re:Purely *Functional* Data Structures

[MooseByte]

"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

[Michael Iatrou]

Have you tried Microsoft Press?

Re:Purely *Functional* Data Structures

[I_Love_Pocky!]

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.

Re:Purely *Functional* Data Structures

[AKAImBatman]

Then how the heck do you know what the teachers are teaching?

I check in on the various curriculums every now and then. Some still teach data structures and information theory, but the trend is toward "Learn C++/Java in 30 days" type of books disguised as text books. Even more telling is how many people get a passing grade in comp-sci (Some even get Masters Degrees!) and couldn't explain what a linked list is to save their lives. The usual excuse is, "well, we didn't cover that." (Which of course they did, but the student still somehow got a passing grade.)

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.

Comp-Sci is great. I love the concepts of comp-sci. My mother actually gave me my first book on data structures when I was 10. (Old college textbook.) It's just too bad that comp-sci isn't very well taught anymore. 90% of the current crop of comp-sci students should probably be flunked.

Why am I replying to a troll??? Oh well, I feel better now.

You feel better about yourself because you labeled a valid opinion as a troll? Dude, you need to get out more.

Re:Purely *Functional* Data Structures

[Anonymous Coward]

I love comp-sci for what it actually is, which is not programming.

If only every comp-sci major realized they were majoring in a Science not a job training programe.

Re:Purely *Functional* Data Structures

[GoofyBoy]

>Why am I replying to a troll???

How many people comment on legal, economics, politics or cultural issues yet don't have a law, economics, political science degrees or even have an idea except what they watch on TV.

Troll? I think his comment is pretty typical of slashdot.

Re:Purely *Functional* Data Structures

[pclminion]

Comp-Sci is great. I love the concepts of comp-sci.

Wow, it's really great to see a spectator who appreciates our sport. Sadly, merely looking up to someone does not magically transfer their knowledge into your skull.

It's just too bad that comp-sci isn't very well taught anymore. 90% of the current crop of comp-sci students should probably be flunked.

Sorry, you don't have the authority to sit on the sidelines of a field you admit you having no training in, and criticize the methods by which it is taught. Not to even mention that gigantic generalization you make by assuming that whatever your limited experience of CS teaching methods is must be how it's taught everywhere.

You feel better about yourself because you labeled a valid opinion as a troll? Dude, you need to get out more.

You need to get out more. I suggest college as a worthwhile destination.

Re:Purely *Functional* Data Structures

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

Re:Purely *Functional* Data Structures

[AKAImBatman]

You think I don't know comp-sci? Oh dear, we seem to have a pickle here. I must have chosen the wrong profession, because I could have sworn I was leading teams of developers, doing my part to change the fact of Java gaming, helping design better database drivers, competing in competitions to pack the most into 4K, building better tools, and generally spending my time trying to knock some sense into these idiots who didn't pay attention when they were getting their degrees.

I didn't get a degree, but I did take the hard way of learning comp-sci. I spent years of my time studying the various texts and papers that students *should* be studying. Some people complain that, "well you can't be a *true* comp-sci professional because you didn't pay for this piece of paper." I just shake my head at their insecurity and offer to help them solve whatever their current problem is.

There are my credentials. Take them or leave them. My only recommendation is that you don't underestimate what I can do, or what I have done.

Re:Purely *Functional* Data Structures

[AKAImBatman]

You're barking up the wrong tree. I tend to comment on Nuclear Sciences and propulsion as an interested amateur. Software architecture, development, programming, and yes, Computer Sciences are all part of my chosen profession.

Re:Purely *Functional* Data Structures

[EnderWiggnz]

or, if people realized that computer science wasnt a science at all.

Re:Purely *Functional* Data Structures

[AKAImBatman]

Hmmm... seems my weblogs say that people have been checking my links. Now it's just a countdown to those who start throwing around slurs like, "you don't know anything about calculating algorithms to execute at O(n), O(log n), O(1), etc.", "game programming is not real comp-sci!" (tell that to my collision algorithms or research into better timing methods), or "that's just programming, comp-sci is REALLY about...". (hint: it's about something that's just a intangible as code)

3... 2... 1...

Re:Purely *Functional* Data Structures

[cthrall]

Well, here's the thing. You're making claims about comp sci programs that ain't true. I got my bachelor's in comp sci from UMass, and our first class covered linked lists in Pascal. This was followed by Scheme and an intense algorithms class. We weren't taught languages, we were taught concepts.

People aren't slamming you, just your inaccurate statements.

Re:Purely *Functional* Data Structures

[Laxitive]

Dude, you can't assume somebody doesn't know what they are talking about just because they don't have some certificate of formal education. Jesus, I've been through CS at a "good" university, and there's nothing I see there that precludes somebody getting a good grasp on it on their own.

-Laxitive

Re:Purely *Functional* Data Structures

[AKAImBatman]

Actually, it's a bit more like engineering. There's a scientific aspect to it, but also an artistic aspect. The scientific aspect can tell you how well your algorithm works. The artistic aspect is that deep-down human intuition that develops newer and better algorithms. The artistic side obviously becomes even more prominent when you begin real-world development, since real-world development begins to take into account such concepts as maintainability and adaptability.

Re:Purely *Functional* Data Structures

[pclminion]

"you don't know anything about calculating algorithms to execute at O(n), O(log n), O(1), etc."

Knowing what the term means, and knowing how to actually prove that an algorithm is O(x), are two different things. Can you prove that general sorting cannot be less than O(n log n)? This is fundamental. If you can't do it, you do not know computer science. (Flip side of coin: if you can, then you are at least heading the right direction).

"game programming is not real comp-sci!" (tell that to my collision algorithms or research into better timing methods)

A hobbyist tinkering in the garage does not a scientist make. Put out a publication comparing your methods with other known methods. Give theoretical upper and lower bounds on run time, memory usage, jitter, etc. Criticize yourself and explain the defects in your methods. Submit it to peer scrutiny. That's science.

Re:Purely *Functional* Data Structures

[AKAImBatman]

got my bachelor's in comp sci from UMass, and our first class covered linked lists in Pascal.

1. When?
2. Some good schools still exist. However, they are few and far between.
3. Assuming you received your degree within the last 5 years, let me ask you this: How many people in your class passed even though they couldn't program their way out of a paper bag?

Yes, I'm frustrated. I frustrated that a comp-sci degree today is so meaningless. As a young adult, I had entered the market expecting that those who had completed their degrees would know far more than I did. While some knew more through experience, most would hack at things until they worked. Despite having degrees, none of the knowledge stuck. By working smarter, it was a very short period of time before I was leading teams of programmers. 50% of my time I would spend educating my team, 50% I would spend on core development while they handled the less tricky areas. (e.g.: I would create core business logic, then let my team develop the GUI and interaction with that logic.)

I have to say though, the hardest thing I ever did was my first project where I was required to direct the developers without writing a single line myself. I think they kind of looked at me like one of their professors. "Why does this fuddy-duddy want it done this way? Wouldn't it be faster and easier to just do it this way?" Of course, there was method to my madness, but it was only shown months later when major changes to the system were reduced to minor changes. :-)

But back on topic. I have no problem with comp-sci degrees or those who obtain them. I have a problem with their devaluation.

Re:Purely *Functional* Data Structures

[AKAImBatman]

Can you prove that general sorting cannot be less than O(n log n)? This is fundamental. If you can't do it, you do not know computer science

Yes, I can. And that's my point. I learned how when I was given my first book on data structures. It was a little weird at first, but if you're going to do things right, you have to know the math behind them. In fact, modern computers long ago made me give up the desktop calculator. Trying to develop for the processing power of today requires numbers far beyond what my old desktop calculators could do. It's too bad, because it was so convenient to not have to switch windows. And yes, I'm too cheap to get a decent scientific calculator. :-)

Put out a publication comparing your methods with other known methods.

You mean like this one? Looking back at it, I should have taken the time to clean up the english. I was so excited about my algo, that I just pushed it out. :-)

Keep an eye on Java Developers Journal for an article on logging. They wouldn't let me publish a pure research paper, but I was able to squeeze in a dissertation on using ThreadLocals for multiplexing a stream.

Does anyone know any *good* comp-sci journals? Dr. Dobbs looks promising, but I had already promised an article to JDJ.

Re:Purely *Functional* Data Structures

[EnderWiggnz]

geez... engineering is applied science.

computer "science" is a branch of mathematics, and not a particularly easy one.

Re:Purely *Functional* Data Structures

[Charvak]

I dont think anyone has yet proved that the sorting cannot be done in less than O(nlog n). Though it seems commonsensical. I maybe wrong but if someone can cite some result I will be happy to look at it.

Re:Purely *Functional* Data Structures

[AKAImBatman]

Take the statement: "engineering is a form of applied science." and change it to "programming is a form of applied mathematics". Does it make sense?

Engineers have to apply science to make their designs work. Engineers who fail to do so invariably fail in their work. However, an engineer without any intuition will never be able to accomplish a revolutionary engineering feat.

Programmers have to apply mathematics. Programmers who fail to do so invariably fail in their work. However, a programmer without any intuition will never be able to accomplish a revolutionary programming feat.

Re:Purely *Functional* Data Structures

[AKAImBatman]

There's a good attempt at it here. Granted, it's not so much a true proof as it is an argument against. But that's why they're called theorms. Someone might come along and show it to be wrong or find a loophole.

That being said, most real world algorithms focus on best or common case. Worst case can often hurt (sometimes as bad as O(n2)), but data is usually prearranged in such a way as to allow for much faster sorting than a general algorithm.

Re:Purely *Functional* Data Structures

[aafiske]

Actually I'd prefer a book on Purely Fictional Data Structures. You know, like Hobbit Hair Queues and Keebler Elf B-Trees.

Sorry, I'll stop now.

Re:Purely *Functional* Data Structures

[jacobm]

Not true, It has been proven, at least if by "sorting" we mean "comparison sorting" where we only know how to compare two objects (the statement is provably false by the existence of faster algorithms for versions of the problem where we get more information). This is a fundamental result of computer science and is a typical (and important!) topic of study in algorithms classes. See PlanetMath's article on the subject for a proof.

(Incidentally, I tried to track down a citation for the origin of the proof but failed. Anybody know to whom this result is due?)

Re:Purely *Functional* Data Structures

[cthrall]

> 1. When?

Graduated '97. After I left, the dept built a brand new building and judging from the alumni paper, it's still a quality program.

> 2. Some good schools still exist. However, they
> are few and far between.

I was lucky enough to stumble across UMass. I think the difference lies in the overall goal: produce a programmer who knows how to create a Visual C++ project vs. a Computer Scientist who knows how hash tables and linked lists really work.

It was hard work, but I really appreciated the focus once I left school and entered a Real World job where I was expected to hit the ground running.

> 3. Assuming you received your degree within the
> last 5 years, let me ask you this: How many
> people in your class passed even though they
> couldn't program their way out of a paper bag?

I can't really think of anybody who couldn't program that ended up graduating. There was one class that I took twice that some people never made it past. A bunch of people who started the program didn't finish it.

Re:Purely *Functional* Data Structures

[Charvak]

Exactly my point. It is very diffcult to prove a lower bound on any problem. I remember my professor telling me that though it seems natural that the matrix multiplication cannot be done in less than O(n^2) but nobody has proved it yet.

Re:Purely *Functional* Data Structures

[AKAImBatman]

You know, all of these arguments have gotten me thinking. Does anyone remember the last time a major mathematical concept was introduced to computer science? The most recent paper I can think of that fits the criteria is probably the one on the Burrows-Wheeler Tranform. Other than people tossing around concepts online and research into encryption, I can't think of a single newer paper.

I did have a new compression algo a few years ago, but I decided not to publish it after I found out that it couldn't do as well as gzip.

Re:Purely *Functional* Data Structures

[AKAImBatman]

Graduated '97.

Ah. See, that's *just* before comp-sci really started to go downhill. Many schools at the time were already bowing to the the market demand for C and C++ programmers (not necessarily a bad thing), but it wasn't until 98-99 that the big stink about "programmer shortages" caused schools to start rushing through students.

I know it's hard to believe (seems like yesterday), but it's been about seven years since you graduated. I haven't even been married that long! (5 years) :-)

FWIW, I'm starting to wonder if programming and comp-sci should be split at schools. Programmer would be more of a "technical degree", allowing computer science schools to produce tomorrows computer architects and researchers.

Re:Purely *Functional* Data Structures

[I_Love_Pocky!]

See, you really don't know what comp-sci actually is. Neither do most of the people posting here. I think I finally see what you mean when you bash on most comp-sci undergraduate programs. They have a lot of focus on stuff that isn't comp-sci (i.e. programming). That doesn't mean that everything you learn while getting your degree is comp-sci. It is important to teach programming in the first year, because understanding how to program helps give a foundation for learning computer science.

In no way is comp-sci engineering, or even applied mathematics. It is a branch of mathematics that deals with computation. When it is applied you get a form of engineering (typically software engineering), but that doesn't make comp-sci engineering. You could spend a life time working in comp-sci and never write a line of code.

I suppose in your post you didn't directly state that computer science is applied mathematics, but from who you were repling to it seemed to me that you were implying that programming and comp-sci were the same thing. Which they aren't (admitedly I didn't know that when I started my degree).

You have had serveral posts here since my initial one, and I think they all basicaly come at this wrong. You seem convinced that getting a computer science degree is worthless because most of the recent grads you are exposed to can't "program their way out of a paper box." Just because you have been successful (I will take you at your word on that) with out a degree doesn't mean that you wouldn't have benefited from getting one. I don't think you have any right to be making the generalization you have been making. A CS program will lose its certification if it doesn't teach theory (which it should, because that is the only part of the degree that is actually CS).

The theory is the hard part, and a lot of grads get away with out having properly learned it. That isn't the fault of the instiution. If you learn something for a test, and then forget it, that is your problem, not the university.

Re:Purely *Functional* Data Structures

[Alizarin Erythrosin]

In the course of getting my CS degree, I had a programming languages class that demonstrated how functional languages have their uses in a very real way. The first assignment was to write a boolean expression parser in C. The second assignement was to do the same in ML. Then Prolog. My Prolog program was 3 lines long. The C program was much, much longer and much more complicated too.

Personally, I am self taught in most languages I know. I took CS because I like to program, but I knew what the degree really was. I learned a bunch of techniques for analyzing algorithms and various other language-independant techniques.

I figured I'd get a software programming job after I graduated, but I didn't want a mindless job. I like to solve problems, so I was hoping for a job where I could program tools to solve particular problems or automate jobs. No "write this part of this project, do it this way", more like "I need X to do Y." That's what I love about programming.

Re:Purely *Functional* Data Structures

[demi]

Wish I had some mod points. As Dijkstra said:

Computer science is as much about computers as astronomy is about telescopes.

We are stuck with the term "Computer Science" but would probably better be served by "Computational Science" or something like that.

Note: I'm a programmer, not a computer scientist, and perfectly happy to be one.

Re:Purely *Functional* Data Structures

[I_Love_Pocky!]

I didn't think he was a troll either, or I wouldn't have replied in the first place. I was merely refering to the fact moderators had labeled him has a troll. I figured that perhaps they were right, and that I shouldn't even be bothering with a reply. I'm glad I did reply though, because he had plenty of interesting things to add to his original comment.

He isn't a troll, and his original message should be moded up accordingly.

Re:Purely *Functional* Data Structures

[AKAImBatman]

See, you really don't know what comp-sci actually is.

I think I may be coming across as incorrect because of the various concepts that get mixed up when referring to comp-sci. Comp-sci is, as you say, an extension of mathematics dealing with computation. Programming is the modern equivalent of a computational machine.

However, when a student finishes comp-sci, they should be capable of one of two things:

1. Using the mathematical concepts they have learned to go into software development. In specific, compilers, operating systems, distributed computing, etc. are all covered by comp-sci degrees. Thus I expect that someone who enters software development should be capable of at least applying the data structures they've learned.

2. Go into mathematical research. Get grants to develop new concepts and algorithms that may be useful to software development, or advance current information theory. (Oh the stories I have about battling information theory, let me tell you. Don't you just hate how making information more compact - even if you make it implied information - makes it no longer compress as well? :p)

My frustration comes from the fact that graduates can do neither. All they *really* want to do is make some instructions execute in order. (Some have some serious problems with that. :-/) They have no appreciation for *using* comp-sci to do their development right. Let's say you ask a typical programmer the following question:

A named property is a name that is associated with some type of information. Most often, named properties are used to store settings by name. For example:

screen-res=1024x768

The part before the '=' sign is the name, while the part after is the value of the property. Access to these properties must be as fast as possible. Which of the following data structures would you use?

a) Hash table
b) Linked list
c) Binary tree


The answer most commonly received form graduates is, "what are those options?"

Follow me so far? Almost as inexcusable are the types who complain that "object references" are really just a fancy name for pointers. Just like methods are actually just functions. If these kids had half a clue that a function is actually a variation of the "mathematical function", they might better understand what they're doing.

"Hey look! I wrote a C program that writes 0xFFFFFFFF to 0xA000 and a pixel appears on the screen! I found it by randomly writing bits to different points in memory!"

*sigh*

Re:Purely *Functional* Data Structures

[thestarz]

Am I the only one who saw "Purely *fictional* data structures"?

Re:Purely *Functional* Data Structures

[natet]

Where I went to school, the less "popular" programming paradigms were largely ignored, not just by the students, but by the teachers as well. Lisp and others were mentioned in our programming langues class, but all of our programming assignments used Java. The only class that used anything besides C, C++, or Java was the AI class which used Lisp.

Re:Purely *Functional* Data Structures

[sketerpot]

I think it may be possible to get pretty far on borrowed intuition. For example, I'm learning some computer science on my own. The other day I wrote my second symbolic differentiation program, and it was pretty elegant---mainly because I remembered the organizational plan from a textbook.

Still, I wouldn't bet on it. It could be that you can only go so far with borrowed aesthetics. But it may be farther than I would think.

Re:Purely *Functional* Data Structures

[I_Love_Pocky!]

I'm starting to wonder if programming and comp-sci should be split at schools.

For the most part I think that is actually a really good idea, and the programming degree should be called "software engineering." I think some schools actually already do this.

Re:Purely *Functional* Data Structures

[geek42]

Dammit - you stole my witty response! Well, except the bit about the Keebler Elf B-Trees. That's just silly.

Re:Purely *Functional* Data Structures

[LewsKinslayer]

I'm a student at UC Berkeley. I know what a linked-list is. Our classes deal heavily in the theoretical, rather than churning out C/C++/Java programmers, as you've stated. Many campuses have extremely high standards for their CS programs.

If I were given the choice between two people, one who had a Master's in CS, and one who "first got an algorithms book at 10, and really learned CS great on his own," the CS graduate is the clear choice. Hint: Despite your claims, you can't get a Master's degree in CS without knowing what a linked-list is.

You paint with a pretty broad brush. Perhaps it's your insecurity at having never earned a degree that causes you to attack the methods of teaching used in higher education. Just because people didn't learn CS "the hard way," (your way) that doesn't mean they aren't learning it, and learning it well.

BJ

Re:Purely *Functional* Data Structures

[AKAImBatman]

The first assignment was to write a boolean expression parser in C. The second assignement was to do the same in ML. Then Prolog. My Prolog program was 3 lines long. The C program was much, much longer and much more complicated too.

Sounds like the compiler theory classes. Shouldn't be too much longer until they introduced you to sorting the operators and operands into reverse polish notation. Recursion is a much easier solution, but it's also very important to understand RPN. ;-)

Personally, I am self taught in most languages I know. I took CS because I like to program, but I knew what the degree really was. I learned a bunch of techniques for analyzing algorithms and various other language-independant techniques.

Good for you! I hope you make the most of your comp-sci degree. If you pay enough attention, you should be able to pass up 90%+ of the existing developers on the market. It will still be very difficult getting a job in the current economy, but once you have your foot in the door you should be able to go far. Just remember: work smarter, not harder!

Re:Purely *Functional* Data Structures

[Saltation]

>Wow, it's really great to see a spectator who appreciates our sport. Sadly, merely looking up to someone does not magically transfer their knowledge into your skull. [...] You need to get out more. I suggest college as a worthwhile destination.

This HAS to be a troll, surely. Apart from the pointless abuse, the attitude is asinine. It's almost a parody of the problem the above poster said he'd observed-- "you criticise my mad skills? FAH! Observe my PIECE OF PAPER, fool."

For the record, I have 3 degrees and don't choose to sneer at people who "merely" know more than I do about something by virtue of actually having done it.

--
Sal

Writings: saltation.blogspot.com
Wravings: go-blog-go.blogspot.com

Re:Purely *Functional* Data Structures

[Saltation]

Another troll, surely. Boy, aren't there a lot of them about today.
http://books.slashdot.org/comments.pl?sid=97498&ci d=8456964

--
Sal

Writings: saltation.blogspot.com
Wravings: go-blog-go.blogspot.com

Re:Purely *Functional* Data Structures

[pinka]

Can you prove that general sorting cannot be less than O(n log n)?


Oh yes it can. It all depends on your model of computation. You are thinking of the situation where you are only allowed comparisons. If you are allowed to do bit-twiddling, and know that your objects are bounded in size, you can do better than n log n

Re:Purely *Functional* Data Structures

[I_Love_Pocky!]

My frustration comes from the fact that graduates can do neither.

And my frustration comes from that gross generalization.

I graduated last May, and I know the answer to your question is a) Hash table, and I would have known that when I graduated. A properly deployed hash table has a O(1) search time (That is not to say I would necessarily think a hash table was the best choice to store name value pairs, but it is the fastest).

Even if my answer to your question is incorrect in your estimation, I clearly learned what all three of those things were in my first year of CS. Any institution that gradauated someone who doesn't know these things should be ashamed, and I just don't buy that they do.

How many of these supposed graduates have you actually talked to? Did they actually graduate? Was it a university, or just a 2 year trade school??? What was their GPA? I can't believe it could have been more than a 2.0 (on a 4 point scale).

Re:Purely *Functional* Data Structures

[KlomDark]

Oh bullshit, I wrote an O(n+1) sort back in 1991. You terran humans have sludge for brains.

Re:Purely *Functional* Data Structures

[AKAImBatman]

If I were given the choice between two people, one who had a Master's in CS, and one who "first got an algorithms book at 10, and really learned CS great on his own," the CS graduate is the clear choice.

Sir, you are a student. How many developers have you actually tried to hire? I've given dozens of interviews, and actually hired several I later came to regret. Trust me. Degrees are not worth anything more than the resume they're listed on.

You paint with a pretty broad brush. Perhaps it's your insecurity at having never earned a degree that causes you to attack the methods of teaching used in higher education. Just because people didn't learn CS "the hard way," (your way) that doesn't mean they aren't learning it, and learning it well.

No, it's honest to God real frustration with the market. I *expect* someone with a comp-sci degree to know what they're doing. (Or at least I used to.) But the waters got really muddy with the Internet boom. Suddenly, a lot of people started showing up with degrees that simply couldn't do their jobs. Now I've pretty much always expected to have to train a graduate. While they should understand theory, they're also going to have to understand things like software maintenance and problem analysis. But they need a foundation in theory to do that.

Perhaps things are really getting better. The economy has forced a collapse of the "dot com supplier" market, and it has been awhile since I've seen someone who was trying to trick people into doing their homework. I'll have to keep my eyes open and maybe form a new opinion.

Re:Purely *Functional* Data Structures

[I_Love_Pocky!]

What is wrong with picking popular imperitive languages for the programming assignments? It isn't very easy to grade an assignment if everyone uses their own language of choice. Most people feel comfortable with imperitive languages, and they are the most widely deployed.

In true theory courses you don't do any programming anyway.

Re:Purely *Functional* Data Structures

[I_Love_Pocky!]

it's also very important to understand RPN.

I love my HP calculator!!! I learned about stacks and RPN before I even started CS.

Re:Purely *Functional* Data Structures

[AKAImBatman]

And my frustration comes from that gross generalization.

Indeed, it is a gross generalization. Unfortunately, it's pretty much true of most comp-sci majors who's resumes land on my desk. I'll grant you that the good ones may be getting filtered out by the powers that be (sometimes I just want to shoot HR departments).

Here's something I want you to consider. People who truly love a field will tend to attempt to congregate with others who love the field. Thus we both have met here. We might have met over at JavaLobby, or on Usenet. But we met because we like this field. Now the only reason we have met is because the Internet allows us to condense distances. In real life, you will often meet very few people in your area who will share your interest and be proficient in that interest.

I graduated last May, and I know the answer to your question is a) Hash table, and I would have known that when I graduated.

Very good. But then again, I wasn't trying to test you. :-)

A properly deployed hash table has a O(1) search time (That is not to say I would necessarily think a hash table was the best choice to store name value pairs, but it is the fastest).

*teaching cap on*

While a hash table can have an O(1) search time, it is sometimes desirable to accept an O(2) or O(3) search time in exchange for delaying a rehash. Rehashing the table is a very expensive operation and should be avoided if possible.

*teaching cap off*

Sorry, you seem to have triggered my automatic, "how to apply comp-sci to software engineering" response. :-)

Even if my answer to your question is incorrect in your estimation, I clearly learned what all three of those things were in my first year of CS. Any institution that gradauated someone who doesn't know these things should be ashamed, and I just don't buy that they do.

Sadly, they don't. I have to run right now, but suffice it to say that I have hired people before based on their apparent understanding and excellent school references. Unfortunately, sometimes they aren't taught well and sometimes they cheat the system. Finding a way to determine that is still something I'm working on.

Re:Purely *Functional* Data Structures

[Anonymous Coward]

Well, according to Knuth , at the top of his news page, there will soon be a new journal -- ACM Transactions on Algorithms -- which may be just what you're looking for.

Re:Purely *Functional* Data Structures

[be-fan]

Its as much a science as theoretical physics is. It is, to a large degree, applied mathematics.

Re:Purely *Functional* Data Structures

[pclminion]

While a hash table can have an O(1) search time, it is sometimes desirable to accept an O(2) or O(3) search time

That statement just proved that you have no idea what the O() notation means. Please, take off the teaching cap, you're going to hurt somebody.

I'm starting to wonder if you are, in fact, a very good troll. You refer to Dr. Dobbs as a "computer science journal," you make references to nonsensical concepts like "O(2)", you claim to have made a "publication" which actually turns out to be a poorly spelled posting on a programming discussion board, and you do all this as you criticize actual computer science students for not having learned anything in school.

That so many people have fallen for it thus far is utterly amazing to me.

Re:Purely *Functional* Data Structures

[be-fan]

You would be really surprised how low the bar as slipped these days. Where did you go to school, anyway? There are schools turning out good computer scientists, but there are a whole lot more churning out Java programmers.

Re:Purely *Functional* Data Structures

[RevAaron]

Surely you mean to say that functional languages don't have mutable objects, rather than "updatable variables." I mean, what the hell do you mean by "updatable variables?"

In Haskell, I can assign the value 5 to a variable x with "x = 5". And I can certainly "update" that variable by later saying "x = 10".

Re:Purely *Functional* Data Structures

[AKAImBatman]

You refer to Dr. Dobbs as a "computer science journal,"

No, I referred to it as a promising place to publish. I don't know any good publications any more. It suddenly occurred to me today, that most of the serious journals have disappeared. There used to be journals for every concievable area of comp-sci. They all seem to have died in the 90s.

you claim to have made a "publication" which actually turns out to be a poorly spelled posting on a programming discussion board

Poorly spelled? A little rough, but I could have sworn I checked my spelling. In any case, what I was doing is what comp sci is about. Solving computational problems. In this case, my algorithm was an attempt to solve an inaccuracy in the computation domain of time. The timer that comes with Java (System.currentTimeMillis()) is only accurate under Windows to within 10-50ms. My solution was to latch onto the leading edge of the square wave, thus giving the program an accurate amount of time to execute. Previous solutions either tried to guess the appropriate timing, or used methods which produced random results and caused the system clock to drift.

That statement just proved that you have no idea what the O() notation means. Please, take off the teaching cap, you're going to hurt somebody.

*chuckle*

Have you ever coded a hash table? Or understand how they work? A hash table is basically a virtual array of all possible hashes for an object or string. Thus if you were using a 16 bit hash, your hash table would be 65,536 items long. Here's the problem: you don't want a 64K array, and you most certainly don't want a 4 Gig array (32 bit). As a result, a smaller array is chosen and the remainder operator is used to scale the item to the actual table size. This has one unwanted side effect: sometimes the hash items will collide.

Unfortunately, the cost of a rehash (create a larger array where they don't collide and reinsert all the hash table items) is extreme, and should only be done if absolutely necessary. This gave rise to most hash tables being designed with the ability to hold more than one item in a slot. If a collision occurs, multiple items will be stored, and multiple items will be searched during retrieval. Generally it's best to only allow 2 to 3 collisions in a hash. If you start having more collisions on a given hash, it's probably time to rehash the table.

And that sir, is how hash tables can have an O(2) or O(3) worse-case lookup time.

Now here's my challenge to you, sir. Explain the difference between a reference and a pointer. Then we'll see how well you were paying attention in your own comp-sci studies.

Re:Purely *Functional* Data Structures

[I_Love_Pocky!]

I went to Washington State University, which is hardly a 1st teir school. I can't imagine that there are so many other schools that are so crappy. But then I wouldn't put much stock in a person's degree if they didn't have a respectable GPA to go along with it. Just because you go through school doesn't mean you did well.

As far as Java goes, it wasn't taught at all in my ciriculum (there was an optional java course for those who didn't feel they could learn the language on their own). In some of my higher level classes they gave us the option of using Java on some assignments, but C/C++ was always acceptable.

Why the attack on Java by the way? I for one think it is an excellent language in some situations. Sytactically it is very similar to C++, and I had no trouble picking it up. I find it to be very intuitive, and a decent choice for many application domains. Garbage collection has its place, particularly in multi-threaded applications (the extra book keeping of ensuring that every thread is done with some object before freeing it in C++ is often more trouble than it is worth).

Re:Purely *Functional* Data Structures

[Roydd McWilson]

I know you're a troll and/or an idiot, but as a courtesy to any other readers:

There used to be journals for every concievable area of comp-sci. They all seem to have died in the 90s.

Check out any of these places for a start:

• ACM Publications
• IEEE Computer Society Publications Center
• CiteSeer

Have you ever coded a hash table? Or understand how they work? ... hash tables can have an O(2) or O(3) worse-case lookup time.

We all know what a hash table is. You apparently don't know that O(f(n)) = { g(n) : \exists k . \forall n . g(n) <= k f(n) }, thus O(1) = O(2) = O(3). Using this definition, the statement "g(n) = O(f(n))" is an overloaded synonym for "g(n) \in O(f(n))".

Explain the difference between a reference and a pointer.

They are essentially the same thing. Perhaps you're referring to the fact that you can't perform arithmetic operations on the address associated with a reference in languages like C++ or Java. But that's a property of the language's type system, not of the English words "reference" and "pointer."

Re:Purely *Functional* Data Structures

[AKAImBatman]

I also think that Java is a first rate language. However, I think his point is that schools today are churning out "programmers" for whatever the popular language of the day is. They started with Visual Basic for awhile, but when Java became popular the market ended up being flooded with people who could supposedly program in it. The trouble is that C/C++ at least had a higher barrier to entry. Not just any fool could write a program without crashing their computer. Java's object model and garbage collection take care of all that making it easier on real programmers, and lowering the barrier to entry for programmer-wanna-bes.

Re:Purely *Functional* Data Structures

[xteddy]

f(x) = O(g(x)) as x approaches infinity means that

lim_x -> infinity abs(f(x)/g(x)) = c, where c is constant.

So it's bullshit to write something like O(2)
because you can multiply the c with 2 and you
would get another constant. Those functions
would thus belong to the same class of
asymptotic behaviour: O(1).

Re:Purely *Functional* Data Structures

[Anonymous Coward]

While a hash table can have an O(1) search time, it is sometimes desirable to accept an O(2) or O(3) search time in exchange for delaying a rehash. Rehashing the table is a very expensive operation and should be avoided if possible.

O(1) means constant time, and it includes variables that don't vary predictably based on 'n' (rehashing time, the page system, memory cache, register scarcity, synchronization overhead, etc.).

Any constant should be fine to indicate that the order of the algo is not related to the size of the data set, but in practice using anything other than '1' for the constant makes you look a bit foolish.

Re:Purely *Functional* Data Structures

[pjt33]

Depends on your matrices. If you assume dense matrices, the proof is trivial: you can't output Theta(n^2) numbers in less than Theta(n^2) time.

Re:Purely *Functional* Data Structures

[pjt33]

[I]t has been awhile since I've seen someone who was trying to trick people into doing their homework.

I still see it all the time at the Java Developer Connection Fora, or whatever Sun has renamed them now.

Re:Purely *Functional* Data Structures

[Anonymous Coward]

To multiply a pair of n x n matrices you have to at least examine every element of the matrices. Therefore Omega(n^2) is a lower bound for matrix multiplication.

Re:Purely *Functional* Data Structures

[greenrd]

Ah, so you can say x = x + 1? Excellent!

Remind me again, just what is the difference between functional and non-functional languages?

Re:Purely *Functional* Data Structures

[Anonymous Coward]

Can you prove that general sorting cannot be less than O(n log n)?

Can you? The best known lower bound for sorting is the trivial Omega(n). The standard proof for the Omega(n lg n) lower bound is for comparison sorting only.

Re:Purely *Functional* Data Structures

[I_Love_Pocky!]

Oh, I agree with that completely.

While we are on the subject: Visual Basic is the most ass backwards language I have ever seen. I would rather throw all high level constructs out the window and program everything in assembly (quite fun in its own right anyway) than have to do another project in VB.

Re:Purely *Functional* Data Structures

[AKAImBatman]

Ack, my math is rusty. But IIRC:

Standard hash table:

O(1)

Addition of an array at each hash:

n = number of items in list
m = maximum number of collisions

thus:

O(1 + m)

Thus if m = 2:

O(1 + 2)
O(3)

Perhaps I'm getting it wrong, but I do believe that's a valid solution.

Doh! I remember, now. O(n) ignores constants. Thus O(n) = f(n) = n + n2 + 1 would equals n2, but O(n) = f(n) = 1 + 2 + 3 would be equivalent to O(1) since none of them grow. Thus the hashtable equation of f(n) = 1 + m = O(1,m) = O(m). What I meant to say is to only allow O(m) to reach 2 or 3 before you rehash.

Okay, I suppose I've said something stupid for today. Time for me to rest. :-)

Thanks for the links, BTW. And no, references and pointers are quite different. If I get the time I'll dig up an old discussion I had on it.

Re:Purely *Functional* Data Structures

[stephentyrone]

As noted above, this is obviously false for sparse matrices. Consider a special case: I can trivially multiply two diagonal matrices in O(n).

More general question: given sparse matrices stored in some compressed form, with some bound on the number of non-zero entries, is there an algorithm to multiply them in time O(n^2)? It's *not* clear that there isn't.

Re:Purely *Functional* Data Structures

[stephentyrone]

sorry, that was meant to read "time less then O(n^2)".

note to self to use "preview".

Re:Purely *Functional* Data Structures

[forgotmypassword]

Does anyone know any *good* comp-sci journals? Dr. Dobbs looks promising, but I had already promised an article to JDJ.


While technically not a journal, if you want good peer review and to get your name more recognized in your field, then lanl.arXiv.org is great for physics, math, and I assume the comp-sci section is good too.

Re:Purely *Functional* Data Structures

[Anonymous Coward]

Granted, it's not so much a true proof as it is an argument against. But that's why they're called theorms. Someone might come along and show it to be wrong or find a loophole.


No, a theorem is correct by definition.

A theorem is not the same thing as a theory (in the scientific method). You obviously do not know what the fuck you're talking about.

If you say you have a theorem and someone finds a mistake, then he is NOT disproving the theorem he is simply classifying your attempt as nonsense. You never had a theorem to begin with in that case, you merely thought you did. For example: there is a theorem that says that a^n + b^n = c^n has no solution for n>2. If someone finds a mistake in the Wiles paper, then it is no longer a theorem, just another failed attempt. A theorem's existence is based entirely on its correctness.

Scientific theories on the otherhand are based from experimentation and are simply "proposals" that may be found to be incorrect or imprecise. Theories may become laws, but even those may be shown to be incomplete: like the law of gravity.

Re:Purely *Functional* Data Structures

[ninjadroid]

Your dragon style cannot compete with my phoenix style!

Re:Purely *Functional* Data Structures

[be-fan]

Well, I don't put a lot of stock in GPA either. There is way too much variation between schools that try to go easy on their students GPA, and schools that relentlessy trash their students GPA. I think the best thing to do is skill-drills during interviews, to see how much they really know. I've found that people who look great on paper absolutely break down in such a situation.

If you graduated several years ago, I wouldn't be surprised that Java wasn't taught. It wasn't highly-hyped language at the time. Schools that teach mainly Java are much more prevalent these days where its all the rage. There are holdouts, still (kudos to MIT for doing their freshmen classes in Scheme according to the SICP) but not enough.

And the I wasn't really attacking Java. I think its a silly language, but it can be useful because of its vendor and library support. My point was more that its currently a fad language, and in response many places are graduating Java programmers just to feed the market.

Re:Purely *Functional* Data Structures

[Genghis Troll]

And I can certainly "update" that variable by later saying "x = 10".

Not within the same scope you can't; you'll get a "conflicting definitions for x". And another 'x' in a different scope is not the same 'x' in any way, any more than two local 'x's in two different c functions are the same. You can assign different values at different times to an 'x' in a c function, but you cannot in Haskell.

There's not even any such thing as "later" in Haskell unless you are inside a monad, but that is, in fact, (part of) the point of monads: you give up purity/referential transparency in exchange for things like explicit sequencing.

Re:Purely *Functional* Data Structures

[Anonymous Coward]

Just for the record, my degree is in "Computational Science". The distinction can be made, unfortunately my old University no longer does so, as they've now joined the "Computer Science" crowd.

Re:Purely *Functional* Data Structures

[warrax_666]

One fundamental misunderstanding you seem to have is that O("something") is a function. It's not. It's a set of functions.

Therefore you cannot say stuff like O(n)=f(n). I know that this notation is sometimes used (inaccurately) in the litterature, but it should be f(n) \in O(n) where \in is the set membership symbol.

Re:Purely *Functional* Data Structures

[andrew cooke]

i was so worried about this post i eventually resorted to cormen et al. the section on counting sorts finally let me sleep soundly.

Re:Purely *Functional* Data Structures

[Anonymous Coward]

Not that anyone's listening anymore, but:

Yes, you can say that, but the result may not be what you would expect from an imperative language. For example, in OCaml:

# let x = 10;;
val x : int = 10
# let f y = x + y;;
val f : int -> int =
# f 100;;
- : int = 110
# let x = x + 1;;
val x : int = 11
# f 100;;
- : int = 110

Try that with a global x in C (or similar) and you'll get a different result...

Re:Purely *Functional* Data Structures

[Anonymous Coward]

Primes in P was a pretty important result that was more recent than Burrows-Wheeler. BWT was like ten years ago, people have not just been sitting on their asses all that time. Go to a library and look through the research journals, there's tons of stuff that has come out in that time. Don't rely on the front page of Slashdot to tell you about all of the recent advances in CS.

Re:Purely *Functional* Data Structures

[Anonymous Coward]

O("something") can be a function and it is not inaccurate to write O(n)=f(n). Details follow.

The definition of O partitions the set of of functions mapping R->R into equivalence classes. Ok, so let's choose a representative element from each equivalence class and label them g_i(n), where i ranges over some appropriate index set I. Now O is a function mapping functions from R->R onto {g_i(n):i \in I}. In particular if we suppose that g_i(n) = n for some i, then we can quite easily write O(5n+6) = n. There is no inaccuracy or ambiguity, or anything else at all to worry about here.

Now, people don't actually do what I wrote above though(at least I can't think of anyone who does). What they do is to write a definition something like "f(n) = O(g(n)) iff ...". This lets them write 5n + 6 = O(n), and 5n + 5 = O(n). Therefore 1 = 0? But it doesn't. Why? Becuase in this context the '=' symbol does not function like the '=' symbol that we all know and love, and even though it looks like we are treating O as a function, we are not. This may be annoying, and it is pretty much guaranteed to confuse neophytes, but strictly speaking it is not inaccurate. This is commonly referred to as an "abuse of notation".

Over where I work

[Anonymous Coward]

Management prefers dysfunctional programming.

I don't even see the code..

[laurent420]

blonde... brunette..

Nice Review!

[jaaron]

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. Another aspect of programming worth investigating.

Re:Nice Review!

[jdavidb]

I hate to disagree, but I don't feel there was a lot of content. I'm very interested in functional programming and would have liked to know what sort of topics are covered in the book and get a sneak peak at the "how-to" behind representing data structures in a purely functional language. Instead I got an introduction to lazy functional languages followed by an introduction to functional languages. Good material, to be sure, but about the only thing I got on the book's specific content was that it requires you to know big-O notation and has an introduction to functional languages that really doesn't completely suffice if you've never seen functional programming before.

Re:Nice Review!

[Savatte]

the only thing I got on the book's specific content was that it requires you to know big-O notation

My pr0n-loving eyes momentarily perked up, but that was a false postive. I should have known, this being a discussion about coding. Oh well, back to "work"

Re:Nice Review!

[YoJ]

This is one of my favorite books, and is largely responsible for me switching from math to CS. I had done C and Java programming before, but I always considered programming (and computer science) a messy but fun engineering activity akin to woodworking. When I read this book, I got a glimpse of the "true meaning" of programming.

I would recommend this book to programmers that have a couple years experience with imperative or OO languages, who have also taken an introductory course in algorithms. A motivated reader does not need experience with ML, but having taken some sort of "Programming Languages" class that spends a day or two on ML is very helpful. I found it the most rewarding to learn ML and start programming in ML while reading this book, then attempting to implement the data structures in the book myself to use in small projects.

If you don't know any functional languages and don't want to learn them, this book will not be helpful and you probably won't get enough motivation from the book itself to understand what it's talking about. If you don't really know functional languages but are willing to give them a try, this book is ideal. If you already know one or more functional languages well, you should try to read Okasaki's papers on functional data structures before getting the book. Of course you might want the book too.

Re:Nice Review!

[jdavidb]

If you don't know any functional languages and don't want to learn them, this book will not be helpful

I do know functional languages a little, and I very much want to learn more. I've got a bit of scheme and lisp under my belt and a vague understanding of what they offer; I would certainly enjoy adding ML and OCaml, too. More importantly, I'd love to see concepts of how to use a functional language in practice to represent data structures.

Judging by the table of contents that somebody else posted in the comments, the book does sound helpful. The original review, unfortunately, was not. He failed to talk about the book itself and let me, an interested programmer who already knows what a functional language is, know why I should read the book.

Re:Nice Review!

[jdavidb]

I don't see how it's "flamebait" or "troll." Apparently functional programmers can't see past "defense of the functional paradigm of programming."

Don't you understand? I want to be one of you; I want to be a functional programmer. I want to know what this book is about and if it can help me get into functional programming. I already know there's something special and wonderful to be gained from the functional paradigm. I don't need an introduction to functional programming or a defense of its merits. What I need is a description of what's in this book. (My thanks to the user who posted the book's table of contents. That was far better than the review.)

I guess some folks are so busy dividing up the world into "friends" and "enemies" that they can't figure out how to just provide information. Obviously, since I didn't rave about how great the review was, I must be an enemy of functional programming and deserve to be modded down.

How can this review be so great when the reviewer didn't even talk about the book? I'd probably willingly agree the book was great if I could know what was in it, but this review told me next to nothing. The people who've said the review is great are really commenting on the quality of the book, not the review; almost all of them say they've already got it.

Re:Nice Review!

[sfogarty]

I'm inclined to agree... but hopefully I can help. This book is my bible, given as my primary interest is functional algorithms. The topics covered are, as you might expect, data structure based, and focused on 'concepts' rather than 'reference'. He doesn't give complete implementaitons of a lot of the structures, leaving it more as an excercise (there is no deletion in the red-black trees), and there is a lot of analysis. The first bit discusses basic imperitive data structures, and how to code them functionally, making it not too hard to start with if you're not familiar with the topic... not to say that you shouldn't already know functional programming and data structure design. The two 'big' (read new) things in the book are layaway ammortization, which can be used persistantly, and a discussion of math-inspired structures deriving from binomial heaps. If you want more information on it, feel free to email me.

Re:Nice Review!

[pyrrhonist]

It doesn't have anything to do with anime either. ;)

O'Camel

[Robert Webb]

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

Re:O'Camel

[Anonymous Coward]

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

Re:O'Camel

[colmore]

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

[smittyoneeach]

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

Re:O'Camel

[Anonymous Coward]

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.

Re:O'Camel

[Nick of NSTime]

In the olden days, people pronounced "Linux" the same way they pronounced "Linus." The 'e' in the poster's comment was phonetical.

Re:O'Camel

[Linux_ho]

Yeah, but how do you pronounce Linus? For example, in Finland, it's pronounced "Leenus"...

Re:O'Camel

[Mr Smidge]

I personally say the less abbreviated, "Objective Camel".

Re:O'Camel

[Anonymous Coward]

It is pronounced:

[Homer Simpson Voice] Ohhhhhh, Camel!

Re:O'Camel

[Anonymous Coward]

The American name "Linus" is pronounced Line-us. The natural English pronunciation of "Linux" is therefore "Line-ux." Of course, Linus himself pronounces linux as "linnix," and since the word is his creation it only seems appropriate that we should adopt his pronunciation.

Re:O'Camel

[Tom7]

In the US it's usually pronounced "Oh Camel", since it comes from "Caml", which is pronounced like the animal.

Re:O'Camel

[sjlumme]

It's pronounced "oh camel", i.e. *not* as a fictitious Irish surname but as an analogue to ACaml, BCaml, CCaml...

The big difference between OCaml and Lisp/Scheme is that even though both are *strongly* typed, that is, you can never, say, reference memory address pi becaus a float is simply not a pointer, they work it in different ways. Lisp/Scheme is dynamically typed, like Python, and stores the types with the values, which are checked at runtime. OCaml is statically typed, which means it does not need to store types in tags, but analyzes your program at compile time to ensure "type safety".

On the one hand, this gives a performance win. On the other hand, it makes programming slightly more painful at times. The expression "if x=3 then 5 else 2.0" is not acceptable to the OCaml compiler, because it cannot determine its type; the expression (if (eq? x 3) 5 2.0) is perfectly acceptable to a Scheme compiler. The advantage of this, it is claimed, is that most programs without well-defined types are buggy anyhow, so it helps you write good code.

Note that the same performance win can be had from not having the language be very precise about types at all, and randomly allowing dereferencing of integers and multiplication of pointers. The archetype for that, of course, is C, which is considered *weakly* typed (a.k.a. "wrongly typed"). This has the disadvantage that programs can behave unpredictably and cause system crashes very easily. If an OCaml or Scheme program ever segfaults, let alone causes a bus error, that's a bug in the compiler. If a C program does that, well you all know what that means...

Just to confuse you a little more, there's yet another distinction to be made, which is between explicitly and implicitly typed. A language such as C or Java is explicitly typed, meaning that you have to declare variables and functions as being of a certain type, although the explicit types in C are mostly sugar and can always be overridden. Python and Scheme are implicitly typed, that is, you don't mention any types, which is not a big deal, since there really is only one type. All right, backtrack. I just said they had type tags, and now I say there's only one type? The answer to that is one of terminology. From a theoretical perspective, if any slot can contain any value, there's only one type (like Java's Object).

Now OCaml is statically, strongly *and* implicitly typed. That means that it will check at compile time that there can be no type errors, and you don't even have to mention the types. Say you write a funtion in OCaml like this: let f x = 2 * x . Then it will derive for you that it has type Int -> Int. This is accomplished through a piece of higher math called Hindley-Milner type inferencing.

If you are interested in this sort of stuff, I strongly recommend Lambda the Ultimate (lambda.weblogs.com), which is always full of programming language reading material, both on a very abstruse theoretical and on a very practical level.

Re:O'Camel

[Linux_ho]

The American name "Linus" is pronounced Line-us. The natural English pronunciation of "Linux" is therefore "Line-ux." Of course, Linus himself pronounces linux as "linnix," and since the word is his creation it only seems appropriate that we should adopt his pronunciation.

Right, but "Linux" wasn't derived from an American name. It was derived from a Finnish name, which is pronounced "Leenus". Anyway, I think we're agreed on the appropriate pronunciation. :-)

Re:O'Camel

[Anonymous Coward]

How can this be flamebait?
(Or, as the French say, flambeaux.)
Every word the parent said was true.

Re:O'Camel

[Anonymous Coward]

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

So that would be oh-cam-WAH?

Misread Headline

[glarvat]

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

Re:Misread Headline

[avante]

Fictional data structures has it's strongest applications in the game software domain, where you need to model fictional characters, creatures and places. Very valuable. Very valuable indeed.

Re:Misread Headline

[yerfatma]

They're especially good for handling release dates.

Re:Misread Headline

[ClooD]

non mentionning Frictionnal Data Structures, very good at storing Adherences

Not a typewriter

[JoshuaDFranklin]

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, so you really could have rewritten that part of your review...

Re:Not a typewriter

[ornil]

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

Re:Not a typewriter

[GoofyBoy]

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

Re:Not a typewriter

[Anonymous Coward]

Lazy evaluation also seems to be the method CmdrTaco uses to decide if a story is a dupe or not.

Re:Not a typewriter

[Jagasian]

Lazy evaluation does not reorder execution. Lazy evaluation is sequential and deterministic.

Re:Not a typewriter

[sfogarty]

Only where there are dependencies of value, especially if you use lazy lets and not just lazy function calls.

Re:Not a typewriter

[Anonymous Coward]

This article you linked to is the most prolix, boring piece of crap I have had the misfortune to attempt to read lately.

Re:Not a typewriter

[sketerpot]

I'll say. Have you noticed that, despite the fact that there's no real reason to, people stay with keyboards that seem almost designed to slow people down when they're typing in 1337 5P33k3? They put all the numbers up at the top of the keyboard! That's why I use the d00dv0ra|.

Re:Not a typewriter

[Jagasian]

If you visualize your program as an Lamport style optimal sharing graph, then lazy evaluation is simply reducing the first redex on the leftmost path from the root of the program. Hence it is always sequential and always deterministic.

Re:Not a typewriter

[sfogarty]

Not sure what that is, but if I have two int lazy_t's returned, which have side effects when evaluated, I can evaluate them in any order.

let x : int lazy_t = f foo in
let y : int lazy_t = f bar in
force x; force y

or
force y; force x.
The side-effect order can be changed.

I like any language

[donnyspi]

that supports GOTOs. Those are the best!

Re:I like any language

[Waffle Iron]

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

[Anonymous Coward]

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

Re:I like any language

[Anonymous Coward]

What is this GOTO you speak of?

Re:I like any language

[Christopher H]

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

Re:I like any language

[Waffle Iron]

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

Sure it is. It lets you warp over to another unrelated part of your program. Except it's weirder, because it lets you kind of go "backwards" in time as well by returning to an older program state (while handing the "past" program a piece of data from the "future" you're exiting). Kind of like an exception, but it can jump anywhere, not just up the stack frame.

In fact this interesting page dedicated to call/cc describes:

At its heart, call/cc is something like the goto instruction (or rather, like a label for a goto instruction); but a Grand High Exalted goto instruction.

Re:I like any language

[Anonymous Coward]

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

You just did, numb-nuts.

Re:I like any language

[Anonymous Coward]

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

Tail recursion is still recursion. Goto is harmful to the programmer's thought process, not to the computer.

Deep down, all loop and if/else constructs use gotos as well. Moving the instruction pointer without storing a return address? GOTO!

Re:I like any language

[Tony-A]

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.

Hmmmmm, that's enough to give an unfair advantage over raw assembler on assembler's own turf.

Re:I like any language

[Scorillo47]

Sure :-)

I give you a more challenging problem: given a language X that doesn't support GOTOs, can you write a preprocessor to create the extended language that supports GOTOs?

Re:I like any language

[sjlumme]

Given proper tail recursion, goto's are completely equivalent to function calls. Look at the following example, written in an imaginary C-like language start: twiddle(); if (...) {goto f; } else {goto g;} f: tweedle(); g: twaddle(); goto f Now with function calls (I'm going to use Scheme syntax here, but don't be scared): (define (start) (twiddle) (if ... (f) (g))) (define (f) (tweedle) (g)) (define (g) (twaddle) (f)) You may *think* that every function call is (a) slow and (b) pushes stack, but that's not necessarily the case. The standard paper (good read!) is ftp://publications.ai.mit.edu/ai-publications/pdf/ AIM-443.pdf .

Functionals

[SparafucileMan]

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

[Anonymous Coward]

You go first, we'll catch up.

Re:Functionals

[ill_mango]

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

[SparafucileMan]

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

[e4liberty]

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, and Gary's OpenMCL is a nice free alternative if you don't need the GUI.

Re:Functionals

[Kupek]

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

[Arcanix]

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

[hc00jw]

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

[Anonymous Coward]

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

[Temporal]

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

[Anonymous Coward]

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

[nosferatu-man]

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

[gangien]

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

[QuantumFTL]

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 functional programs are simpler because they directly map to the mathematics of the algorithm given... especially for recursive algorithms!

I believe that often times it's more difficult to program in, but that's hard the same as "complicated".

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.

Actually one of the main problems that is noticed within the functional community is that because there's a lot of recursion and tight coupling between different parts of algorithms, they can be hard to maintain. That's why a lot of people are excited about monads. They allow the use of modularity in a very cool, and appropriately mathematical way! You should check them out of you haven't already, they greatly simplify the task of writing things like interpreters, etc.

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

I'm not really sure that's true. I know people who's first programming language was functional, and they found it equally hard to move to a procedural language - worrying about things like state, ordering, pointers, globals, memory management, bounds checking, interrupts and callbacks and non-persistent data structures, and even manually-implemented laziness.

Advanced features of any language are difficult to learn, but I'd suggest that anyone who knows a little math can learn to write a small but useful functional program as easy or easier than they could in something like C. Not to mention many algorithms are so naturally recursive, but tail-recursion optimization doesn't seem to work well on many C compilers.

It's certainly different though!

Cheers,
Justin Wick

Re:Functionals

[Jagasian]

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

Re:Functionals

[bigbadbob0]

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

[Anonymous Coward]

I was taught a functional langauge before I was taught a procedural one (I learned scheme before I learned java and c). Anyways though, for smaller projects I absolutely love programming in scheme, it has a certain elegance to it that none of the procedural langauges have.

To me though, where the functional langauges lack, from what I have seen, is in the very large projects. I would hate to have to deal with a project that has a huge code base. The program just becomes harder and harder to get your mind around much quicker than a procedural one does. Now, this could just be a scheme thing. I have never programmed in Lisp or Ocaml before. Maybe they have tools and the neccassary structure to make large projects easier, but I know scheme doesn't.

Re:Functionals

[grumbel]

If anything many functional programs are simpler because they directly map to the mathematics of the algorithm given... especially for recursive algorithms!

I have to agree on that, for mathematical and recursive stuff functional languages are great, but how many of this mathematical stuff is really required these days for 'Joey Programmer'? As soon as it gets complicated there is most often a C-Library around that already solves the dirty work (lists, arrays, hash-maps, etc.). Sure there is still a lot of stuff around that can't be simply solved via yet-another library, but isn't quite a lot of code today mainly wiring userinterfaces together (think VisualBasic programmers), ie. rather boring imperative stuff? For me thats the biggest stopping block for functional languages, sure I have seen a lot of nice quick-sort and similar algorithms in functional languages, but I haven't seen much whole programms around written in a functional language, which lets the functional languages often look rather academic.

Re:Functionals

[Anonymous Coward]

(do ((i 0 (+ i 1))
(sum 0 (+ sum i)))
((> i 8) sum))

completely obvious if you know scheme. If you don't know the language you're using.. stop programming in it for christ sakes. It really is that simple.

Re:Functionals

[mattyrobinson69]

Newbies cant read other peoples code?

you do know there's a # button next to your enter key (well its next to backspace on my keyboard0

if the code is to be shared (or is large) it should be commented. its easier to notice bugs if you have comments too.

Re:Functionals

[Anonymous Coward]

Your C code is very poor.

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

You've used the include preprocessor directive but not specified an include file, this is a compiler error. Secondly, you've not specified a return type for main however I'll overlook this as C89 permits "int" to be assumed by the compiler if no type is explicit and "int" is correct in the case of main() (note that this is deprecated in C99). You've also not specified any arguments for main(). The only two choices valid in ANSI C is "void" or "int argc, char ** argv" (and variants thereof). This results in undefined behaviour.

Your use of printf() is questionable too. Primarily, you've not specified a prototype for it. Normally you do this by including stdio.h. Also, you've not included a carriage return at the end of the string. Although this isn't strictly an error on some platforms this will result in no output at all, implementation defined behaviour in other words.

To conclude, you should return a value from main. I know you didn't specify a return type but as I say, "int" is implicitly assumed. For future reference, the only portable values that can be returned from main are "0", EXIT_SUCCESS and EXIT_FAILURE; the last two requiring that stdlib.h be included.

Phew. That's damned impressive gangien. A three line C program and a total of five errors. Congratulations for setting the bar for C coders at an all time low. (and I didn't even mention your crappy formatting).

Re:Functionals

[Another MacHack]

An even better solution is

(define (sum a b)
(* (+ a b) (/ (+ 1 (- b a)) 2))
)

Re:Functionals

[BinxBolling]

I would argue that the dominance of procedural languages grows not out of efficiency of execution, so much out of inertia and network effects.

You see, functional languages just don't offer that much of an advantage over procedural languages. Sure they can allow you to express algorithms much more concisely. But the biggest problem in most real-world programming efforts is not quickly implementing a particular algorithm, but rather, figuring out what algorithm is the right one to implement. Functional can help you a bit here, by making it easier to try out a variety of approaches and contribute empirical data into that decision, but all that really means is that you raise the complexity threshold at which the iterative approach becomes untenable; You never eliminate that threshold.

I was a huge functional language fan, for a long time, but now, actually working as a programmer, I don't find myself thinking that using a functional language would make my job easier or more fun.

Re:Functionals

[Anonymous Coward]

"but I haven't seen much whole programms around written in a functional language" - you haven't looked
And as for "how many of this mathematical stuff is really required these days," I had the same question. So here's what I did. I came up with a "practical" application idea and only allowed myself to implement it in scheme. I was really surprised how efficiently it mapped onto a functional language. Have a hammer and only see problems as nails? NOw, if you only have a functional hammer you'll be surprised how your thinking can change.
Now if only I could find a job programming in a functional language...

Re:Functionals

[Anonymous Coward]

Did you dive into scheme already knowing the language, oh master?

Re:Functionals

[Anonymous Coward]

(1..8).inject(0){|sum, i| sum + i }
('a'..'z').inject(''){|sum, i| sum + i } :(

Re:Functionals

[QuantumFTL]

I have to agree on that, for mathematical and recursive stuff functional languages are great, but how many of this mathematical stuff is really required these days for 'Joey Programmer'? As soon as it gets complicated there is most often a C-Library around that already solves the dirty work (lists, arrays, hash-maps, etc.). Sure there is still a lot of stuff around that can't be simply solved via yet-another library, but isn't quite a lot of code today mainly wiring userinterfaces together (think VisualBasic programmers), ie. rather boring imperative stuff? For me thats the biggest stopping block for functional languages, sure I have seen a lot of nice quick-sort and similar algorithms in functional languages, but I haven't seen much whole programms around written in a functional language, which lets the functional languages often look rather academic.z

Well, if you're just patching together GUI stuff and a few libraries, might as well use Python for everything.

But if you're doing "real" programming, like a simulation or a database or a compiler or basically anything algorithmically intensive, it's nice to use languages that allow you to effectively express the algorithm.

Unfortunately much of my work is highly numerical and doesn't work well outside of FORTRAN/C/C++ but there's plenty of other things functional languages are good for.

I think most programmers do not use functional languages because they have been slow in the past (not so much any more) and most of them are not familiar with it. It seems accademic because only accademics seem to take the time to learn this kind of programming. I dont' think it's quite ready for mainstream yet... but I hope in the next 10 years to see it slowly leaking into other more established languages before finally making a breakout.

That being said, if I were to write a server for something (which is something I've done at my job before) I'd want to use OCaml due to it's robustness and inherent safety (no buffer overflows, etc...)

Cheers,
Justin Wick

Re:Functionals

[Anonymous Coward]

"Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp." ~Greenspun's Tenth Rule of Programming

Re:Functionals

[duffbeer703]

The closer your code is to a business rule the better.

In a procedural language like C or even a language that's a little more "intelligent" like Perl, alot of your time is spent dealing with the arcana of the language.

In a functional language, your focus is on the needs of the application, not reimplementing the linked list for the 1 billionth time.

Re:Functionals

[andrewgaul]

Haskell: foldl (+) 0 [1..8]

Intuitive and obvious if you are comfortable with higher order functions.

Re:Functionals

[vivin]

I tend to disagree. It all comes down to what you want to do and HOW you want to do it. Quite simply put, some things are better done using a functional language, while others are done better with procedural language.

After all, they are just different ways of approaching a problem. A functional language may not necessarily be "easier to read" - that is a relative term. Also, the concept of a procedural language is easier to understand than the concept of a functional one. A functional language like LISP is as much a mathematical system as it is a programming language. And most people find procedure easier to understand that mathematical systems.

Re:Functionals

[ichimunki]

Are you kidding me? In your example, the Perl is the easiest to read. Which is a sure sign of a contrived example-- but, oddly, one which contradicts your assertion. Furthermore I think including the #!/usr/bin/perl bit is unfair, it's not necessary depending on how you call the script... and certainly you've left out the compile step for the other three examples, if they aren't interpreted at runtime.

I will grant that the Scheme is likely to have the easiest syntax to learn, but conceptually it's tougher. It's more like calculus and less like following a recipe. Most of us learn how to follow recipes (i.e. imperative programs) in the real world long before we learn higher mathematics.

If you want a simple, easy-to-read language with a fairly straight-forward syntax, check out Ruby. Of course, raw assembly is pretty easy to read too (BRK, JMP, AND, XOR, etc are not exactly hard on the eyes) and has almost no syntax at all! So measures like "syntax" and "readability" aren't always all that informative.

Re:Functionals

[Tablizer]

Functional languages fucking 0wn. They are, generally, easier to write, maintain, read, understand, and debug than the procedural

Is there any direct *quantifiable* evidence of this, other than "It works for me"? It is hard to seperate personal preferences from universaly objective benefits with these kinds of claims.

For example, can you show that it results in less code? Less LOC or unit changes per change scenario? (And please don't select only scenarios that favor FP.)

Re:Functionals

[sfogarty]

I disagree... they may be harder to learn if you were brought up on imperitive languages, but function code is certainly easier to read than imperitive code.

Re:Functionals

[AuMatar]

You have it the wrong way around. The processor executes a program as a seires of instructions, one following the other, where each instruction is completed before the next one is began. All that math thrown on top of it is a needless complication from whats really happening.

But then again, I majored in computer engineering (hardware design), so maybe I'm biased :)

In the end, any way of thinking about it works, One size does not fit all, use whats best for you. My preference is pure C- I'll tell the processor exactly what I want it to do when, and I don't want it doing anything behind my back or "for me". If I didn't write it, I don't want it.

Re:Functionals

[AuMatar]

If just using the fewest lines possible was the measure of readability and understandability, perl would be king. Most frequently, increasing the expressiveness of a language (how much is done per line) reduces the readability because the compiler is doing more behind the scenes and more knowledge of the code is assumed.

Re:Functionals

[gangien]

lol well I was giving an example i didn't run any of the code at all so for all I know they all may fuck up. Nore did i put much thought into them.

Re:Functionals

[gangien]

OK mr. picky. I had include ;ltstdio.h;gt but I was leaving for class didn't spell check let alone preview my post and forgot that the stdio would get gobbled up by the HTML parsing. There's also a number of grammatical mistakes in the non code part. I believe your pickiness is like taking a 1 minutes example and expanding it to a 10 minute example for no good reason. Yes I know ANSI C and if this was an ACTUAL program i would of not used that code. But the point of my post was not to illustrate proper C code nore to illustrate anything except how tricky imperative languages are compared to functional languages, syntax wise, and I think you've proved my point. Anyhow continue trolling.

Re:Functionals

[Anonymous Coward]

Functional languages are pretty easy to learn and I pretty much use Ocaml all the time at work on Windows(!). I just decided to start rewriting all the stuff we had in perl in Ocaml (but using the ocaml-perl lib for regexps).

Experience has shown that the Ocaml code is definitely more maintainable when going back and trying to figure out what the heck is going on. But on a LOC basis it ends up around 1.5-2x larger than the perl equivalent; but if you restructure significantly you can sometime get to 1x - 1.2x larger but you got to think functionally!!!

The other thing I found is that once I figured out how to get the native COcaml interface working, I was able to start writing real apps (ie db/messaging etc - I work at an investment bank) a lot faster than I could previously in C++. Especially when it came to things like multithreading and DB/XML/Messaging, being able to write concise code really helped.

Oh yeah the fact that, in real life situations, as opposed to microbenchmarks, I got something that ran typically faster than the C++ equivalent just because people cannot write big apps that are consistently cache friendly throughout their runtime, unlike the Ocaml which pretty much seems to...

Just my experiences....

Re:Functionals

[Dasein]

Ack! Using examples with side-effects to demonstrate functional programming! Sheesh. Try this on for size (from the About Haskell 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[l] <= p))
l = l+1;
while ((h > l) && (a[h] >= p))
h = h-1;
if (l < h) {
t = a[l];
a[l] = a[h];
a[h] = t;
}
} while (l < h);

t = a[l];
a[l] = a[hi];
a[hi] = t;

qsort( a, lo, l-1 );
qsort( a, l+1, hi );
}
}

Re:Functionals

[Anonymous Coward]

The C version is in-place and the Haskbell version is not. As your link notes:

In effect, the C quicksort does some very ingenious storage management, trading this algorithmic complexity for a reduction in run-time storage management costs.

Re:Functionals

[LittleDan]

I learned very functional, very OO, and low-level procedural languages around the same time (around a year span; I don't think a year is enough time to mold your brain to a single paridigm, is it?), and I'm still learning. From what I've seen, you can't use one paradigm for everything. My first language was TI-83 calculator basic, and while it's extremely low-level, I did much better on it than I would on Haskell or Io (a language where everything is an object, but there are no classes).

Later, I tried to learn a number of other languages but Python, a non-functional language, was the only one I could learn. Python doesn't have any gotos and doesn't in any way resemble calculator basic, but it's still very good for beginners. Later, I learned Haskell, which seemed very flexible and high-level but I/O was a whole new language, and very difficult to use at that. Haskell was the best for math and theoretical stuff, though. Its use of static typing while also having generic functions and parametric polymorphism helped avoid many bugs. Lazy evaluation is great but sometimes it can be hard to grasp the flow of a program.

I also learned Io, a language where everything is an object and a prototype. Unlike something like Java, which some advocates of Functional, procedural, or "table-oriented" programming think all OO languages are like, there is no difference between classes and objects, anything about objects can be changed at runtime, and not everything has to be put in objects. Io and other object-oriented programming languages are in some cases better for larger projects, where you might otherwise need to resort to using variable prefixes or internal use of a module system within a module in order to prevent name colision. There are also times when in defining a datatype in a functional language, it seems like it would be more useful to have mutable variables, something which object orientation handles nicely, even if sometimes variables are mutated when new ones should be made.

It would really be inappropriate to say that functional programming is always better or object orientation is always better. Depending on the situation, you need to choose which pardigm is best.

Daniel Ehrenberg

Re:Functionals

[gangien]

the Perl is the easiest to read.

For this example sure.. But can you honestly say that's normally the case?

It's more like calculus and less like following a recipe. Most of us learn how to follow recipes (i.e. imperative programs) in the real world long before we learn higher

I think this is wrong. I think you would have an easier time teaching someone, with no programming experience, a functional language than you would an imperative one.

If you want a simple, easy-to-read language with a fairly straight-forward syntax, check out Ruby. Of course, raw assembly is pretty easy to read too (BRK, JMP, AND, XOR, etc are not exactly hard on the eyes) and has almost no syntax at all! So measures like "syntax" and "readability" aren't always all that informative.

I've never seen ruby, and I don't know what paradigm it is in, but from the other languages i've used and seen, I'd much rather trace through functional language's code than any other's code.

Re:Functionals

[cgibbard]

I'd write it as
sum [1..8]
in Haskell, where sum is defined by the standard prelude as sum = foldl (+) 0
which means essentially "fold the operator + in between the elements of the list, with 0 at the end to deal with the empty list case". That is [1,2,3] would be turned into ((0+1)+2)+3 = 6.

Most of the loops that people tend to write are usually to express one of a few basic idioms. Having functions as first class allows these idioms to be recorded and reused without the need to rewrite them all the time, which is really handy. These are referred to as higher-order functions, and cover things such as map (applying a function to each thing in a list), fold (mixing in an operator as above), zip (pairing elements from two lists with each other), and filter (picking things out given some condition) being a few of the most common.

Part of the trick to becoming good at functional programming I think is learning to not just think "I'm going to loop over this list.", but to recognise straight away what sort of goal your "loop" will accomplish. Almost all of the time, you won't have to think about direct recursion, because what you're trying to do is an application of a higher-order function, letting you express directly what you want to do with the list rather than thinking so much about what happens to the individual list elements.

- Cale Gibbard

Re:Functionals

[Anonymous Coward]

which is confusing. And not obvious. But as for other people's code, that is always the case.

Get at least 5 years of experience with C and other people's code is pretty easy to read unless they're really trying. Their intentions are more difficult, but that's what comments are for, at least in theory.

Re:Functionals

[gangien]

umm this is not just a C thing. get used to any language and reading other's code becomes much easier. C is a rather simple and clean, and I love to use it when I think an imperative approach is needed. But I still stand by my original post.

Re:Functionals

[3.1415926535]

Too complicated! Try

sum [1..8]

(sum is defined in the Prelude as pretty much exactly what you wrote)

Re:Functionals

[andrewgaul]

Too complicated! Try sum [1..8]

sum is merely a utility function, also found in imperative languages such as Python: sum(xrange(1,9)) . Using fold demonstrates the power of functional languages. Python has a weak version of fold called reduce, which may be removed in future versions because it is not idiomatic and slower than the imperative equivalent due to tradeoffs in Python's implementation. One cannot treat operators as functions and is forced to use operator.add or the lambda equivalent: reduce(lambda x, y: x + y, xrange(1,9)) .

A neat paper on fold is A tutorial on the universality and expressiveness of fold.

Re:Functionals

[pjt33]

Sure, but if you want a non-in-place version in C, you have to introduce mallocs and error handling for malloc returning zero. Hardly helps make things clearer.

Re:Functionals

[Anonymous Coward]

Well, memory leaks, segmentation faults, etc.
usually result from what you DID NOT put into your code. I don't want them but I will get them in C when I don't ask for them.

Yeah, C is really nice...

Re:Functionals

[Anonymous Coward]

This is a good example of the difference between imperative and functional thinking. I don't think it demonstrates the superiority or fundamental clearness of imperative thinking or imperative programming. Functional programming becomes more intuitive and natural with practice (just as imperative did, if you'll think back).

The way you wrote sum is indeed a little confusing, but any good student of SICP would have written:

(define (sum a b)
(define (iter sum a)
(if (> a b)
sum
(iter (+ a sum) (+ a 1))))
(iter 0 a))

Which is conceptually very clear. Well, maybe if you've read the first 2 chapters of SICP.

BTW, the great book on Scheme (and programming in general) which I've mentioned is Structure and Interpretation of Computer Programs, aka Wizard Book. See http://mitpress.mit.edu/sicp/. Someone should really write a review of SICP on /.

Richard

Re:Functionals

[addaon]

If scheme is the simplest language you know, learn forth.

Re:Functionals

[Temporal]

I said "most", not "all". Obviously it's a matter of opinion.

Re:Functionals

[AuMatar]

Strawman argument. They just aren't that common. I've studied the defect database at work. Less than 1% of over 1000 defects in the past year were due to memory problems. And the average time to fix them (measured as the differnce from the time the defect was submitted to time it was closed out) was far less than that of the average bug. Yet I have never seen a Java or other "higher level language" (rofl at that one) that didn't have a large number of problems due to what the compiler and/or interpreter did that was hidden from the coder.

Re:Functionals

[rmathew]

(display "Hello World") -Scheme

Just:

"Hello World"

would do in a Scheme interpreter.

Re:Functionals

[sjlumme]

What exactly do you mean by "updated for modern functional languages"? The main functional languages these days are Common Lisp, Scheme, OCaml, SML, and Haskell.

The original LISP machines ran Zetalisp, which had a lot of Common Lisp in it already, but still had quirks like dynamic scope. Most Lisp Machines derived from the MIT lineage (Symbolics, LMI and TI) supported Common Lisp as soon as it came around; Xerox had a competing system that ran Interlisp.

Now, if by "modern" functional language you mean ANSI Common Lisp or Scheme, I agree: it would be really awesome to have a modern Lisp Machine around, hopefully a little more RISC-like, but with the same basic philosophy. If you mean some ML dialect, though, the use of special-purpose architecture seems limited to me. The main win of the Lisp machines was that they could deal with typed values; in ML you don't need those, since types are dealt with statically.

Lastly, let me just shamelessly promote my Lisp Machine webpage:

http://www.its.caltech.edu/~weel/lispm.shtml

Re:Functionals

[Anonymous Coward]

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.

It is only confusing because you do not know what you are doing:

guile> (use-modules (srfi srfi-1))
guile> (apply + (iota 8 1 1))
36

Re:Functionals

[szap]

In perl,

# Imperative
sub qsort {
return unless @_;
my ($p, @l, @r) = shift;
$_[0] < $p ? push @l, shift : push @r, shift
while (scalar @_ > 0);
return (qsort(@l), $p, qsort(@r));
}

# Pseudo Functional
sub qsort2 {
return unless @_;
my ($p) = shift;
return qsort2(grep{$_ < $p} @_), $p, qsort2(grep{$_ >= $p} @_);
}

Not that much of a difference. Many functional or functional methods exists in modern "scripting" languages anyway. e.g. Perl's grep, map, sort. Most don't have lazy evaluation though, and "Ease of Understanding" might be lacking in Perl programs :)

Re:Functionals

[SparafucileMan]

Yes, but in math, we get the added benefit of having infinite resources and such ;)

But I see what you're saying about C--if you know the language down to the hardware level, that would work best. But then again the C gets translated to assembly by a compiler, and you can do the same with LISP, provided your compiler is good enough.

Re:Functionals

[Anonymous Coward]

Good. My work is complete now that you realise that your program was poor. Always remember young padawan, poor C code costs lives.

And with that final insight, the great wizard smiled and promptly dissapeared up his own arsehole. Young gangien looked non-plussed however but in time, he will come to realise that the great wizard has taught him a valuable lesson.

Re:Functionals

[Arcanix]

And the award for the most oversimplification of two vastly different paradigms goes to the Anonymous Coward above!

Re:Functionals

[Anonymous Coward]

Always remember the lesson I taught you, young padawan.

Re:Functionals

[Anonymous Coward]

"..C is a rather simple and clean.."

Never forget the humility I taught you young gangien. It is futile to disregard my teachings.

Re:Functionals

[renoX]

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

You're right of course, but it is notheless true, that personnaly I found learning functionnal language quite difficult instead of imperative language, and I'm not the only one.

Plus in the commercial world of today, you're unlikely to have several years of experience with functionnal language..

Academics can have this experience of course, but for some reason, I tend not to value very much academics point of view in this matter: they tend to do different things that in the "real world", such as IHM, database programming, scripts, etc..
That's why we use C and not Pascal today..

Re:Functionals

[gangien]

what now you're gonna respond to all my posts like this? Guess what, I'll go anakin on your ass :P

Re:Functionals

[Foolhardy]

In HP's RPL (reverse polish lisp) used on their graphing calculators, the first example is

<< "hello world" DISP >>

and the second is

<< 0 -> tol << 1 8 FOR i 'tol' i STO+ NEXT >> >>

-note that '<<' '>>' and '->' are single characters, easy to enter using the keypad.

Talk about confusing, if you don't know the language.

What is the world coming to?

[TwistedSquare]

A while ago I read the comments following a Slashdot book review

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

Re:What is the world coming to?

[mdielmann]

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

Ah, but he didn't say he read the review itself. Nor did I, this time.

This was a great review

[jkauzlar]

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

[SparafucileMan]

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

[tcopeland]

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

Learn more than one programming language, preferably many different styles, like scripting, object-oriented, functional, logic, etc.

There's an Artima article 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

[Anonymous Coward]

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.

Re:This was a great review

[SparafucileMan]

I should have included this link:

Perl Contains the Lambda Calculus.

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

[rmull]

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

Re:This was a great review

[andrew cooke]

thanks. another good book (that i should have mentioned - i forgot about it when i was writing that, but just used it a moment ago) is cousineau + mauny's "the functional approach to programming". it's like an ml/ocaml version of the (relatively) famous "structure and interpretation of computer programs".

Re:This was a great review

[Anonymous Coward]

For good comparisons of imperative vs functional approaches check out Ullman's Elements of ML Programming, which is also the clearest introduction to functional programming that I've read, so I can heartily recommend it to novices. He teaches SML in the book, but the syntax is virtually identical to OCaml, so you should have no problem doing exercises in OCaml as you go along (like I'm doing).

For a good comparison of OCaml to Ruby check this out.

Section 4 of this overview of SML is Why You Want to Start Using SML Today, which has some nice high-level comparisons to imperative languages like Java, C and C++.

Re:This was a great review

[Anonymous Coward]

A nice and thorough comparison of OCaml vs Ruby, including:

"I can now confidently say that Ruby and OCaml are at the absolute top of
programming languages. I'm a bit annoyed with the fact the OCaml is in fact
so good the it steals ground from Ruby. Its a bit like a Japanese
sportsmotorcycle compared to a European ditto with the nationalities
reversed..." ...

"The slightly disappointing side of this is, from a Ruby perspective, is that
OCaml seems to be strong also in those areas where Ruby were supposed to be
uniquely strong."

eek!

[happyfrogcow]

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

..must.. resist...

..cannot.. fight.. functional

..language.. tempatation...

*head explodes*

Re:eek!

[Jackmon]

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

Re:eek!

[technomancerX]

LISP = Lots of Insipid, Stupid Parentheses ;-)

The memories...

[kneecarrot]

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

[hc00jw]

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

[johnnyb]

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

[kneecarrot]

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

[Jagasian]

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

[Jagasian]

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

[monadicIO]

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

Re:The memories...

[pHDNgell]

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 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 be quite efficient.

Pretty much anything that loops can be considered recursive though. Take a look at my iteri implementation in OCaml:

extlist. (click on iteri for the code).

BTW, don't worry if you can't read the OCaml documentation just yet. It's very easy to read after spending a brief amount of time in OCaml.

Re:The memories...

[HenryFlower]

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 languages, a common advanced technique is to create an object factory. In pretty basic Scheme, you can create a function that creates an object factory function. It just requires a new way of thinking about programming.

Re:The memories...

[comedian23]

They are using traversing a tree as an example of something that IS recursive and were wondering if you had written other programs which didn't lend themselves quite so easily to a recursive approach.

-Comedian

Re:The memories...

[haystor]

Non recursive problems can be handled with functional languages quite well generally.

After just a few weeks of programming seriously in Lisp, I found it easier to debug than languages I've used for years. The reason for this is that everything is a function. You can unit test practically everything. You can try it out from the interactive loop.

My typical hard to find bugs at the beginning were typically because I was using the language wrong, not because I was using the syntax incorrectly. A good example of this would be using a counter combined with a while loop instead of recursion or my favorite, the loop facility.

Re:The memories...

[ajagci]

Scheme is not a functional programming language, it is very much imperative programming language that supports a functional programming style.

Furthermore, Scheme is more like the assembly language of functional programming; "real" functional programming
languages have much better facilities (type systems, data types,
module systems, type inference, etc.) to support the construction of large software systems.

Re:The memories...

[metamatic]

Of course, there are downsides to ML-style type checking as well... like getting incomprehensible error messages that indicate completely the wrong line of code, when you make a small syntactic error somewhere. I found ML intensely frustrating, whereas I love Scheme.

Not having easy ways to deal with typed heterogeneous data tends to be a bitch in the real world too.

Re:The memories...

[Anonymous Coward]

No.

Re:The memories...

[mahbidness]

At my university, we had to work with both Scheme and ML during the programming languages class. Of the two, I much preferred ML. Scheme solutions just looked kludgy; too many parentheticals, and the car and cdr syntax just irritated me to no end. ML solutions, on the other hand, were just beautiful, especially with list operations(of course). Take this problem for example:

Write a third function reverse that takes a list of any type ('a list) and returns the list with all its elements in reverse order.

fun reverse nil = nil
| reverse ls = reverse(tl(ls))@[hd(ls)];

Two lines. Just concise and elegant. It does feel quite a bit like you're playing hot potato with your final result, though.

Re:The memories...

[Anonymous Coward]

Just to clear up, this is because of the lazy evaluator.

Scheme is an "eager" or non-lazy language. Maybe you're thinking of Haskell?

Re:The memories...

[sml-chicago]

Slightly better would be to use pattern matching instead of hd and tl:

fun reverse nil = nil
| reverse (x::xs) = reverse xs @ [x]

Re:The memories...

[Tony-A]

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?

OK, I'll take a nibble on that one.

In a former life, with an End-of-Lifed FORTRAN compiler and some ASM structural code, I have actually done functional programming that was compiled by FORTRAN. One stunt was to replace an undecipherable FORTRAN program with a brute-forced, top-down, implementation of the definition of what the program was supposed to accomplish. Despite spending almost all its time figuring out what to do next, it was actually a hair faster that the mess it replaced.

Some observations:

If a problem is inherently recursive, the optimum solution is not recursive! You want recursion so you don't run into major problems handling minor stuff. Essentially, recursion allows RETURN to go back to from whence it came, regardless of how it got there and regardless of what else is going on. In non-recursive FORTRAN, recursive CALLs work. Once a recursive CALL is made however, there is at least one RETURN that doesn't.

A trace of the Program Counter doing functional stuff is incredibly uninformative. That is with knowledge of all levels of all parts.

The advantage of functional programming is not with the parts of the system that have been thoroughly analyzed and you know the best way to do it. The advantage is that you state what you need and slop some stuff underneath that's good enough to work in that context. At some point the top-down functional programming has to meet the bottom-up fundamentals. The bottom-up stuff needs to be well-defined, as in the results of all theoretically possible inputs against all theoretically possible states. Unless you do it yourself, it is essentially guaranteed that the bottom-up is not defined to your liking. The definition must include the results of putting 1000 bytes in a 100 byte buffer. There is no good definition. There are a lot of very bad definitions.

I have the impression that functional programming will be much more effective if you can read machine language.

Re:The memories...

[cthugha]

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?

I assume you've coded a lot of solutions that use iteration, yes? Iteration and recursion are the same thing, looked at from a different point of view.

Take the canonical example of finding the factorial of n. In an imperative language you would just use a for loop and an integer counter. Recursiverly, you would just say something like this (using Haskell):

fact 0 = 1
fact n = n * fact (n - 1)

In general, any problem that can be reasoned about using mathematical induction is susceptible to solution both by iteration and recursion.

Translation of Okasaki's sources from SML to OCAML

[bcolflesh]

4.1.8. PureFun

It's all in the constructors

[skybrian]

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

[jaaron]

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

Re:It's all in the constructors

[skybrian]

Well, sort-of kind-of not really. In functional programming, *every* method is essentially a constructor. (It constructs a result, and that's all it does.) Also, all objects are immutable, and many of the objects you're constructing are themselves functions.

The similarity is that an object's properties are always specified at construction time.

Re:It's all in the constructors

[Tom7]

Sure--and also you want a language that makes expressing those transformations easy. Algebraic data types and pattern matching are really convenient for tree-structured data (like parse trees or XML), and higher order functions help you abstract out operations (like mapping and folding) on the data structures. Writing functionally in C is very painful.

Just got this book

[QuantumFTL]

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.

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

[Sparky77]

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

Re:Just got this book

[illustir]

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

[QuantumFTL]

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

[Jagasian]

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

[QuantumFTL]

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

Re:Just got this book

[Anonymous Coward]

A monad is half a gonad.

You're welcome.

Re:Just got this book

[Jagasian]

I have to wonder if there are other Categorical "design patterns" for functional programming.

Re:Just got this book

[sqlgeek]

Oh my. slashdot wants to know what Category Theory is. Where to start?

Category theory is concerned with the study of mappings between objects of a given type (or category). For example: there are mophisms between "groups" that preserve certain group-theoretic properties, there are likewise morphisms between "topological spaces" that preserve topological properties, etc.

Category theory is the study of how these categories are similar or disimilar, and how mappings between them can illuminate surprising relationships between ostensibly dissimilar areas of mathematics. The point at which category theory really took off was when new relationships between group theory and topology took shape and became "algebraic topology".

I forget the author, but one of the best places to start one's study is the book _Category Theory for the Working Mathematician_.

Cheers,
Scott

Re:Just got this book

[jovlinger]

set theory? nah; plumbing!

monads are plumbing.

Re:Just got this book

[Anonymous Coward]

Your post gives the impression that OCaml is purely functional, which it isn't, but I'm sure you know that...

As for first-class functions and closures...they aren't a thing of the future, they exist in most garbage collected languages and have for a while. The major exception is Java, where the design goal seems to be to force people to use classes for everything.

Re:Just got this book

[Jagasian]

Category Theory for the Working Mathematicians has a huge list of prerequisites that most Slashdotters can't meet. It might be the canonical text on the topic, but a better more tractable text would be "Category Theory for Computing Science".

functional algorithms

[sir99]

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

[SparafucileMan]

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

[sir99]

Actually, I adapted the Haskell code from someone's thesis 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)))

Re:functional algorithms

[Anonymous Coward]

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)

PRIME is linear??? When did that happen?

It might be log something, but I forget and am lazy.
Or dreaming...

Re:functional algorithms

[SparafucileMan]

Oops! Sorry, brain fart. I meant PRIME is in P.

Re:functional algorithms

[Mr Smidge]

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 = x * y
> stop = 1
> my x = x
> bottom = my

> but thrust =
> let deeper = minus thrust
> in my bottom (if lubricated thrust then stop else thrust `harder` (but deeper))

Nah, nothing dodgy about that at all..

Re:functional algorithms

[andrew cooke]

i'm curious - what's the c version look like? (the haskell version looks ok to me - it seems to be about n^2 according to timings, and i think that's what you'd expect because the number of tests goes up more-or-less as n).

Re:functional algorithms

[Anonymous Coward]

I don't know Haskell well enough to be able to do this, but googling I find that an implementation is supposed to be:

primes = sieve [2..]
where sieve (p:rest) = p : sieve [n | n <- rest, mod n p /= 0]

I don't have Haskell present to test whether that is O(n*n) or not. If it is, then I wouldn't count it as being the Sieve of Erastothenes.

Re:functional algorithms

[sir99]

I'm too lazy to type it in slashdot, but I put the C version here. It seems to be slightly worse than O(n). Actually, I think I might be able to do better in Haskell using a list of the composites instead of the primes, since those can be generated as a list of multiples instead of using the modulus.

Re:functional algorithms

[andrew cooke]

hmmm. i think your c algorithm is O(n^2) too, but only in the limit of large "count" - then the inner loop is O(n) (in practice, count is not that large, and that inner loop has a very small constant, so that loop is proabably not visible in any timing test with reasonable numbers). but i might not have understood what you're doing, and i'm not 100% sure the inner loop is O(n) even then, because the step size is increasing.

i think it's more likely you're seeing a *huge* difference in constant factors. that's very optimized (i'm impressed) c code - of course that also implies it has a whole pile of restrictions (fixed upper limits on values etc).

i doubt any functional solution is going to give you comparable speed to that code - certainly not at the moment. but you're kind-of comparing apples + oranges (it's a bit sneaky that the c code requires an upper bound from the start).

Re:functional algorithms

[sir99]

The AC seems to have a good description of the efficiency, at least if I implemented it in the standard way. I'm not sure if the C code could be optimized much further. All that bit munging to pack the bitmap costs CPU time in exchange for lower memory usage. OTOH, the improvement in cache hit rate may make up for it.

You can calculate an upper bound on the magnitude of the n'th prime, so you could just replace my sneaky ;-) choice of count with that.

Re:functional algorithms

[Anonymous Coward]

Check out these progressively more efficient implementations of the sieve in haskell (look in the mimencoded file attachment). --Kartik Agaram

I bought this book

[johnnyb]

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.

GOTO is good, but ...

[Anonymous Coward]

... I prefer COME_FROM.

Re:GOTO is good, but ...

[Tablizer]

I dig calculated gotos:

GOTO LINE RANDOM(1, LINECOUNT(CODE_FILE))

I then outsource the debugging to India :-P

Re:GOTO is good, but ...

[3.1415926535]

Oh come on, calculated COME_FROMs are the wave of the future! Get with the program!

Re:GOTO is good, but ...

[Anonymous Coward]

You forgot

RANDOMIZE TIMER

I heard this mentioned on some previous article

[emurphy42]

Microsoft Excel is a functional programming language. Discuss.

Re:I heard this mentioned on some previous article

[catamorphism]

See Simon Peyton-Jones et al's paper "Improving the world's most popular functional programming language: user-defined functions in Excel". (It's just a coincidence that he works for Microsoft Research, really!)

Re:I heard this mentioned on some previous article

[Tailhook]

That was me. It is here.

Online version available

[johnnyb]

Also, since this was this guy's thesis, it's also available online

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

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

Re:Online version available

[Anonymous Coward]

We discussed this book in SU.SOFTW - Russian FIDO group about software engineering - and one found that aforementioned thesis differs from book. It was found that kook discuss a little bit more, for example, RB-trees.

Another Book ...

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

[chamilto0516]

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.

Re:Cool languages, but why...

[Anonymous Coward]

Some of us are wanting to write proofs about computer programs. This would allow you to strip out a number of bug and security issues because you could prove your program did not have any.

Scala

[Channing]

Have a look at Scala 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, like...

[Short Circuit]

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

[GoofyBoy]

Previous message = False.

( Short + accurate ) + communiction = good.

Computer != typewriter.

End of message.

Re:But, like...

[Anonymous Coward]

You must be a devil with the ladies.

Laziness Bad

[firewrought]

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

Re:Laziness Bad

[catamorphism]

That's why some researchers in the field of lazy functional language have developed techniques for "optimistic evaluation" -- basically, the compiler uses strict evaluation until it's determined that the object it's evaluating can't be evaluated strictly (for example, in the case of a conceptually infinite list). You still get lazy semantics, and you have most of the performance benefits of a strict language. See the work of Robert Ennals and Jan-Willem Maessen.

Re:Laziness Bad

[Temporal]

Depends.

a function uses the parameters it is passed most of the time.

Sure, functions you are used to, written in normal, eager-evaluation languages, use all of their parameters most of the time. However, if you had lazy computation available, you might be more inclined to write code in completely different ways that take advantage of that functionality. Those ways might actually be a lot more efficient than you'd imagine. You probably haven't thought too hard about them since you haven't used any lazy computation languages.

Good compilers can do enough optimization to mostly negate the drawbacks of lazy computation. Yes, it will be less efficient if you simply rewrite eager-computation code in a lazy-computation language. But, perhaps there's some other way you could write that code to take advantage of lazy computation to make it faster?

Obviously, the answer to this question isn't simple, and I don't pretend to know for sure which method is "better".

Re:Laziness Bad

[sfogarty]

Big-O wise laziness can NEVER be worse than greedy evaluation. In terms of those nasty constant multipliers, yes, laziness can be slower. But in terms of algorithm design laziness is the only way to create amortized structures that maintain their bounds under persistant use. Consider a normal batched queue (front stack, back stack, reverse when empty). Consider persitantly going back in time to just before a reverse and reversing it again. and Again. and again. Bad.

Re:Laziness Bad

[drgnvale]

That's one advantage of scheme's function-calling semantics over lisp's, IIRC (can anyone confirm?).

Actually, I'm pretty sure that lisp isn't lazy evaluating at all. At least not until I whip out my lazy evaluation macros.

Lisp

[venomix]

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++ =)

Re:Lisp

[Anonymous Coward]

what are you wearing right now?

Re:Lisp

[Sri Lumpa]

>>"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++ =)"

>" what are you wearing right now?"

He is wearing things inside out with his underwear over his pants, that's because Lisp (Scheme included) programmers are Superheroes ;)

But what data structures?

[QuantumFTL]

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.

But I hope you buy the book :)

Cheers,
Justin

Re:But what data structures?

[qui_tollis]

IIRC Osaki said there were some data structures he did not know how to implement in a pure functional language, but I don't think he said which. Are there any obvious gaps in the TOC given by the parent?

Re:But what data structures?

[QuantumFTL]

IIRC Osaki said there were some data structures he did not know how to implement in a pure functional language, but I don't think he said which. Are there any obvious gaps in the TOC given by the parent?

Splay Trees weren't mentioned in the TOC but I haven't gotten thruogh the whole book yet...

He does say that persistent arrays were about impossible to implement functionally except with a horrible access time. Random Access Lists are used instead (forgot to include that in my list).

Not sure what else is missing... I didn't see skiplists anywhere in there or any other randomized data structures, but that might have been a matter of personal taste on his part. He also didn't talk much about perfectly-balanced search trees (expensive in imperitive langauges, rediculously so in functional languages).

Good question though!

Cheers,
Justin Wick

Re:But what data structures?

[Mikkeles]

'Are there any obvious gaps in the TOC given by the parent?'

Graphs and dictionaries/hash-tables.

Re:But what data structures?

[sfogarty]

You cannot have functional/persistent arrays, skip lists, splay trees, or anything that has multiple paths or requires side-effects on reading.

Functional use

[Tenebrous]

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

Re:Functional use

[alienmole]

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

You carry on searching Monster.com for your coding drone jobs, that just leaves more of those six-figure salary jobs, using advanced programming languages, for those who actually have skills and knowledge.

But when your boss ships your job off to the lowest offshore bidder, you might try picking up a copy of something like PAIP or SICP (google for them), and learn some of the stuff you've missed in your education and/or career so far.

A coder's hobby

[Bohnanza]

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

[RPoet]

Yeah, can you imagine working with something you enjoy that much? It's preposterous.

Re:A coder's hobby

[jejones]

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

Re:A coder's hobby

[Anonymous Coward]

I think you mean:

It's what mere programmers do in their spare time.

Uh hello, Matrix quote?

[Ayanami Rei]

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.

Who would have thought...

[exp(pi*sqrt(163))]

...that you can design data structures that parallel the way in which you represent numbers? You mean like this?

Functional Programming missed the boat

[Ars-Fartsica]

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.

Re:Functional Programming missed the boat

[Jagasian]

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 consider a Logic programming language.

Re:Functional Programming missed the boat

[sunwukong]

What about Erlang and Ericsson?

Re:Functional Programming missed the boat

[The Pim]

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

Re:Functional Programming missed the boat

[Kyouryuu]

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 types, such that there is reasonable expectation that if someone codes under a given construct, it will work as needed. Based on UML diagrams, it is also far easier to break part programs using an OOP language and blueprint them. Can you imagine the nightmare of doing a large project like Doom 3 in Scheme, with so many functions defined on-the-fly and passed to and from other functions?

Scheme and others have their place in the world in teaching newcomers to think recursively. This is a very useful way of thinking in any language. Common problems often have very elegant solutions in Scheme, and diving into the mindset of functional programming is essential for any serious programmer. But I believe the nature of the language holds it back. Granted, once you know what you're doing, it's not so difficult. But it would seem somewhat unintuitive to plan and design large commercial projects around these languages.

Re:Functional Programming missed the boat

[PylonHead]

Yes, this is definitely where functional programming shines. This is also the kind of problem that I really enjoy working on... you've got a complex set of data and your code has to do some deep thinking on it to come up with an answer.

OCaml fully supports both functional and imperative styles. I've had a lot of luck mixing and matching styles to solve various problems.

One project was an IRC bot that took requests from irc channels, a web interface, or the console. Juggling the interaction was a no brainer. And I find that when it comes to the actual computational part, the functional style is much more concise and error free.

It's nice to have the best of both worlds.

Re:Functional Programming missed the boat

[pavon]

There is some herd mentality aspect to what becomes popular and what doesn't, partially due to hype and parially do to snowball effect - the more programmers there are for language X the more it make since to use language X for a large project.

But from my experiance, the number one influence of the success of a language are the quality and breadth of the support libraries. You can have the cleanest, most powerfull language in the world, but if someone has already done 75% the work for you in klingon, then you can bet programmers are going to want to use klingon.

Re:Functional Programming missed the boat

[Ars-Fartsica]

But once again, think on a practical level - what is preferrable - right tool for the job, or the tool for which the developer pool is the largest?

If you go with a minority language you are going to be mining a much smaller set of developers. Ultimately you will pay more to develop your code - experts in minority languages are so because they want to differentiate themselves, and that also means more pay. Maybe you will find a ML guru who charges less than a Java guru, but I doubt it. And if you ML expert quits or gets sick, you are in big trouble.

Tools also level the playing field. Maybe the ML guru can get a project done faster using vi and a command line build tool faster than a Java programmer using vi and a command line build tool, but in fact the Java programmer has a huge number of labor-saving tools available that the ML programmer doesn't. These tools matter too.

Re:Functional Programming missed the boat

[Anonymous Coward]

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.

I don't know why, but for some strange reason, the image of RMS just popped into my mind.

Houston, we have a problem...

Re:Functional Programming missed the boat

[iabervon]

Functional programming is too far from how most programmers currently think, but I think there are two ways it will gain popularity. The first is that some more mainstream languages, such as Java and Python, are moving that way. The functional programming patterns of creating a lot of temporary structures which are garbage collected has become more common, and producing a chain of derived structures is better optimized. Now that Java has Generics and closures, it can have first class methods, and list operations make sense. I don't think Java is headed towards actually becoming a functional language, but it is headed towards making functional languages more accessible.

The other thing is that functional languages are much better at describing the behavior of massively parallel systems (like computers at the hardware level) than imperative languages are, so they are likely to because important in ASIC and FPGA programming. (This is because monads, the serialization technique used in functional programming, work well for collections of changes to the state with unspecified relative order, while sequential instructions are bad at representing the range of possible variation.

Re:Functional Programming missed the boat

[Jagasian]

You are right, but it doesn't mean that we shouldn't push for developers to have a broader understanding of programming languages. We need to improve the industry as a whole over the long term.

Re:Functional Programming missed the boat

[MrBlint]

That looks very interesting. Downloading now. Supported on vxWorks too, mmm....it might be just the thing for my current project. If it lives up to expectations I may try to sell this where I work.

call_control ! {dial,2544};

looks a bit simpler to code than

struct CC_MESAGE msg;
msg.source = TASK_ID_SIGNALING;
msg.type = CC_MSGTYPE_DIAL;
msg.length = 4;
strncpy( msg.buf, "2544", CC_MAX_MSG_LEN );

fwk_send_msg( TASK_ID_CALLCONTROL, msg, sizeof(msg);

And that is heavily paraphrased

Monads are trivial.

[Kickasso]

Really. Try this one: http://www.nomaware.com/monads/html/index.html

XSLT

[Black Perl]

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!

Re:XSLT

[Anonymous Coward]

This is a myth. XSLT is harldy a purely functional language, because there are no first class functions there.

In fact, there are no second nor third class functions in XSTL, only templates, which are more alike procedures than functions (cause they don't return useful result - except for dumping it to output stream)

Re:XSLT

[Zagadka]

Your first point made sense, but your second point did not. Returning a "useful result" and dumping to an output stream are logically equivalent when the operation you're performing on said result is concatenation.

For some tasks, they work better

[Duderstadt]

If you look here, 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 language should be obvious.

I don't know if you can do this with Java or not, but if there were such a decompliler, the output would be much easier to work with as in ML than with Java itself.

I Like

[Greyfox]

This one. It runs pretty fast, though it can take quite a while to compile...

mmm, I Don't Know ...

[GNUALMAFUERTE]

Functional Programming sounds to me as Pascal put upside down:
Pascal Doesn't let the coder make mistakes.
This lets the coders make mistakes, and just ignore those ..
This may sound ok, but it helps you create big nasty bugs that will go unnoticed until they popup and ruins your life.
It's actually easier to debug such things in languages like C or ASM.(Not only easier to debug, but also harder to create such a monster)

Complicated Languages

[jefu]

I've been programming for a while now. Spent quite a bit of time coding in C, enough to wire the imperative model happily into my brain. I learned and programmed in other languages as well - mostly imperative - including Fortran, various assemblers, smalltalk, algol, apl, C++, perl, python, java .... And then I learned Haskell. Haskell is one of the simplest languages around, and it can be great fun to use as well. If you want complicated, try C++ or java or perl.

Now what I'd like to see

[OpMindFck]

is Purely Fictional Data Structures.
Just think of the Zen Koan Binary Tree.

same for OOP

[ajagci]

It took OOP nearly 30 years to catch on for good. It took garbage collection nearly 40 years to become widely accepted.

The industry will come around to functional programming eventually: OOP simply isn't up to the task of building large systems that are also reliable and robust. FP is much better at that. I don't know how many more failed space probes, software disasters, and power outages it will take before people catch on to that fact, but it will happen.

Re:same for OOP

[Ars-Fartsica]

It took OOP nearly 30 years to catch on for good.

OO has a long history, that is true, but OO in industrial/practical applications goes back further than you might think. People were "using" it in the 80s. OO is not a post-millennial fashion in tools.

It took garbage collection nearly 40 years to become widely accepted.

That is not a function of the network effects of GC, but rather a function of the performance of the hardware to make GC appear to be invisible.

The industry will come around to functional programming eventually

No one is disputing functional langs are better - in fact I stipulate such in my original post. My point was they have no network effect. Java's ubiquity (or Java-like langs such as C#) probably isn't even done its growth curve. You are at least going to have to wait for Java to go out of fashion before you can hope to get traction for an alternative. Try in 2010. I am not trying to yank your chain, I am just saying that the adoption curve for Java (which has incredible network effects) hasn't stopped growing yet.

Re:same for OOP

[ajagci]

OO has a long history, that is true, but OO in industrial/practical applications goes back further than you might think. People were "using" it in the 80s. OO is not a post-millennial fashion in tools.

In that sense, people have been "using" FP in industry since the 1960's. But OOP only caught on in any real sense in industry in the 1990's, and people are only now getting over the initial enthusiasm.

It took garbage collection nearly 40 years to become widely accepted.

That is not a function of the network effects of GC, but rather a function of the performance of the hardware to make GC appear to be invisible.

No, sorry, but you are buying into the same irrational prejudice that has kept industry from using GC in the first place. Any reasonable GC is, and has for the past 40 years been, no more expensive than your trusty manual C storage allocator. Furthermore, most of the other supposed advantages people ascribe to manual storage managers are myths. Altogether, there has never been a rational reason not to use GC.

Try in 2010. I am not trying to yank your chain, I am just saying that the adoption curve for Java (which has incredible network effects) hasn't stopped growing yet.

I didn't say it was going to happen tomorrow. I think for FP to catch on in industry may take another 20-30 years even. But eventually, it's going to happen in industry because there is no alternative. And smart players can get an early start, in particular since runtimes like CLR actually make a reasonable effort to support it in a multi-paradigm environment.

Great Book

[jefu]

I agree. Okasaki's book is wonderful. I learned so much from it and still pick it up from time to time and learn a bit more. Indeed, it is on my "frequently used" shelf of CS books.

Yup, I'm an academic - but I've also done real programming. Learning the functional programming mindset took some time, and learning to really program in functional languages (I like Haskell as it makes it hard to program non-functionally) took some serious work. I can pick up most algol family/imperative languages in a couple of days, at least enough to feel comfortable and be able to code real problems. Haskell took more than a month to master (maybe about a week to get the basics) but then it finally really clicked (and I suspect the click was probably audible, it was so sudden and revelatory). And my program analysis skills and my programming skills have been all the stronger since.

Okasaki's book not only helped me understand the functional programming model, it helped convince me that there was more to it than just fun languages.

I recommend this book highly for those who are interested in functional programming, or who are interested in learning more about data structures and algorithms on many levels.

Hard to use in the "real world".

[Godeke]

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

[philgross]

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.

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

Re:Took Okasaki's data structures course

[adam613]

I took Okasaki's Software Engineering class at Columbia in 2001. He is a phenominal professor, but Software Engineering is clearly not his primary interest.

In hindsight, I wish I had taken Programming Languages and Translators with Okasaki, and Software Engineering with the parent poster.

The tyranny of momentum: why Ocaml is not popular

[zeno_lee]

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/

Functional JPEG

[Effugas]

http://www.cs.uu.nl/people/jeroen/article/jpeg/

A good example of how terse yet powerful functional code can be: JPEG decoding in a few pages of code. Damn.

--Dan

Letting you in on a little secret

[GodSpiral]

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.

Re:Letting you in on a little secret

[Anonymous Coward]

OOP SUCKS!

Someone who will agree with you:

http://www.geocities.com/tablizer/oopbad.htm

Re:Letting you in on a little secret

[Anonymous Coward]

Voluntary restrictions are beneficial. Just as a spell checker warns me that I seem to be writing a word incorrectly, encapsulation warns me when I make assumptions about how an interface is implemented (which could change).

As for Lua, we already had a surplus of untyped scripting languages (Python, ECMAScript, Perl, Tcl, Ruby). I wish they'd put that effort into something truly novel.

Re:Letting you in on a little secret

[Anonymous Coward]

> Just as non-open source software allows your
> data to be held hostage by the class producer
> authors.

Okay, Karl,if you say so. Down boy, down. Who
gonna stop the Man!

Re:Letting you in on a little secret

[GodSpiral]

encapsulation warns me when I make assumptions about how an interface is implemented (which could change)

Our programs manipulate our data. The libraries we use to transform/manipulate our data should return it to us for our safekeeping. The bank account object you provide for me could lose its withdraw and balance methods, essentially not only allowing me to lose useful functionality (withdraw), but also the main data/information (balance). Your interface implementation could be changed, but not necessarily to my benefit.

Beyond that, though, is the tedium and drudgery of crafting classes and implementing interfaces, which repetitively takes a lot of lines of code to accomplish fairly little.

As for Lua, we already had a surplus of untyped scripting languages (Python, ECMAScript, Perl, Tcl, Ruby). I wish they'd put that effort into something truly novel.

There's an extra level of elegance to Lua, even over python and ruby. It's a bit faster and a lot smaller than the others, and there is a nice implementation on palms Plua

Re:Letting you in on a little secret

[sfogarty]

Going to have to disagree. Java/C++/C# are painful in that way, yes, but smalltalk, for instance, is almost as much a pleasure to use as OCaml. I'm a big FP fan, but OO can be done well.

Re:Letting you in on a little secret

[dswan69]

Quite right encapsulation is a restriction; that is the benefit. It is not popular with code cowboys.

There is no parallel between OOP data hiding and closed source proprietary data formats.

You've misunderstood re-useability.

I like the easy to read C syntax, with semicolons.

A carefully considered object structure saves a lot of time later and does make code easier to maintain. It is not popular with code cowboys either.

Another shootout

[Anonymous Coward]

http://dada.perl.it/shootout/

Mod parent up

[Anonymous Coward]

It's worth noting that PLT Scheme has a really powerful "object" system, that's a lot more powerful than javas. It lets you do structures, objects, classes, interfaces, modules, units, and boxing. These things help get around the insufficiencies of objects. Oh, and they're all (except modules) first class objects.

Good book? Yes. Useful? Not really.

[Junks Jerzey]

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

[Tablizer]

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.

Re:Prefer databases

[boristdog]

You said it brother. I've been putting the weight of my code in DBs for the past couple of years and life has become easier.

You're right that a lightweight, fast RDB engine one could include in one's code would be mighty handy. If I had the skills...

Re:Prefer databases

[Tablizer]

I would note that file systems *are* databases, just not relational ones. Thus, when you put code in a file, you are putting code in a database. I find hierarchical file systems very limiting, and would love to have file systems go relational. There are rumors that MS is working on such. However, non-tree file systems have a longer learning curve, and thus may have an audience limited to techies.

Re:Prefer databases

[Permission Denied]

A light-duty "local" relational engine to complement or replace "big-iron" RDBMS would be nice.

Here you go - sqllite.

Not sure if that's what you had in mind: it still uses SQL syntax to access the database. Alternatives would be something where you express relationships through code. I can't think of any way to do this that is cleaner than a join statement but I'd like to see what you had in mind.

However, sqllite is designed for exactly what you had in mind: embedding within a program you distribute. It supports exactly that subset of sql that I need for common programs and is very easy to use.

I have implemented some of these in Ocaml

[j h woodyatt]

If you're interested in Objective Caml, I have implemented 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.

Re:I have implemented some of these in Ocaml

[sfogarty]

Why is laziness not pure? Lazy evaluation is a very functional feature. I've certainly never heard of it outside of a functional language.

Re:I have implemented some of these in Ocaml

[j h woodyatt]

Because lazy evaluation is really a way of "hiding" the mutation behind a functional representation. What is happening under the sheets, of course, is that a block of memory containing a pointer to a function mutates so that it subsequently contains the result of the function instead.

For the data structure to be "pure" functional, it would have to be constructed entirely out of non-mutable components, and therefore no lazy evaluation would be permissible.

In practice, i.e. in most applications of functional languages, you wouldn't care about this distinction one single bit. In theory, however, you would care about it in the presence of concurrency or in environments where mutation is simply not possible, like when you're streaming into a read-only medium.

Here's what that really means: my Cf_deque.t type can't be used with the Marshall module in the Ocaml standard library, because it's not a "pure" functional data structure. If I had used the Kaplan-Tarjan-Okasaki realtime catenable deque structure (substantially more complicated and costly at runtime, I contend), then it would have been usable with Marshall.

Re:I have implemented some of these in Ocaml

[sfogarty]

Strange. It shouldn't matter, in concurant situations, as long as force is atomic, no? (Not that I'm sure it is, but if it is, then there should be no problems). The entire point of laziness is that it's a side-effect which cannot change the value of any call, so it doesn't matter when it happens. Does your cf_deque.t type use lazy_t or a reference? Now I'm curious.

Re:I have implemented some of these in Ocaml

[j h woodyatt]

Download the code and have a look. (It uses the Lazy module in the standard library, for concatenation only).

Concurrency in Ocaml is an illusion solely for the purpose of providing control inversion. There is one big lock around the entire interpreter (and an equivalent lock in native code). If you use the Thread module (with userland threads or POSIX threads, it doesn't matter which) then you can only get one thread at a time running Ocaml functions. All the other threads have to be blocked (or in the case of POSIX threads, executing outside the Ocaml runtime environment).

The distinction about "pure" functional data structures I'm making with regard to concurrency would require the data structure itself to be distributed among a network of concurrently running processing, possibly hosted on physically different machines. (My implementations don't try to do that.)

(What do I mean by "distributed among a network of concurrently running processes" in the above? Imagine that the references between components of a data structure are not pointers into a memory heap, but are Universal Resource Locators or Message Reference Identifiers instead. That should help you visualize what I'm talking about.)

Re:I have implemented some of these in Ocaml

[sfogarty]

But, assuming there was 'true' concurancy, would lazy evaluation in the presence of an atomic force present any problems? I can't see any, but that doesn't mean much. In the above model I doubt you'd get an atomic force (since the time between 'fetch' and 'evaluate' could be non-trivial), but it's possible. I'm also curious about problems you mentioned with marshalling... are you mashalling data or data types? heh, perhaps we should take to email.

Re:I have implemented some of these in Ocaml

[j h woodyatt]

I can answer pretty clearly in one more message.

1. Making lazy evaluation "atomic" in the presence of concurrency is the generalized problem I was trying to surface. The mutual exclusion lock would destroy the "real-time" property of the deque operations.
   
   
2. Marshall in the Ocaml standard library cannot serialize/deserialize values of type Lazy.t, and that means values of my Cf_deque.t can't be used with Marshall. (This is a trivial issue in practice, because what you would do is convert a 'a Cf_deque.t into a 'a list and marshall the list.)
   

Both of these issues are resolved by using the Kaplan-Tarjan-Okasaki real-time catenable pure functional deque algorithm, but that structure-- to be precise about what I am contending-- has substantially larger constant multipliers in its complexity for the environment profile where I am making the comparison (which I think is a fairly common one). I'm choosing not to pay for pure functional properties where all I really care about is a) functional, b) catenable, c) constant amortized runtime cost for all operations, d) sub-linear worst-case runtime cost (actually I get O(log log N) worst case).

By the way, the Kaplan-Tarjan-Okasaki algorithm is not in the book reviewed in the top-level article.

--

Re:I have implemented some of these in Ocaml

[sfogarty]

There is a real time deque algorithm presented in the book, IIRC. And yes, it's very ugly. I'll have to look into the marshalling stuff. I do wonder if that's not an OCaml thing, because it seems strange that you can't marshall, say, haskell code. Not that I've tried.

The heap algorithms in Scheme

[jasoegaard]

Okasaki's book is delightful. Anyone interested
in data structures owe themselves read his book.

I became so inspired that I implemented all the heap
algorithms in Scheme:

http://www.scheme.dk/heaps-galore/heap.scm

The code contains implementations of the following heaps:

- leftist heaps
- binomial heaps
- pairing-heaps
- splay heaps
- lazy binomial heaps
- lazy pairing heaps
- skew binomial heaps

The documentation is here:

http://www.scheme.dk/heaps-galore/doc-heap.txt

thanks

[gstover]

I had no idea such a book existed. Thanks.
gene

Mathematica?

[gardyloo]

I've just started consciously focusing on functional programming techniques in Mathematica . It's almost religiously advanced in most of the Mathematica texts I've read as being easier to read and, ultimately, faster to program than most procedural algorithms one could implement to do the same things. I've definitely adopted it for some operations on lists and things, but I'll have to get more comfortable with it to apply it to everything I do in Mm . As far as I know, the Mathematica Journal even has a column devoted to solving problems with "one-liners", using only functional programming techniques. (Of course, if one is really interested in it, he could go to Journal of Functional Programming and educate us all.) I'm too cheap to find out for sure.

It seems to me that Mathematica is extremely powerful in this respect: one can choose which paradigm to program in, and successfully mix paradigms, almost to the heart's content, and get useful information out. Of course, the execution speed may not be so hot, but for ease of use, it can't be beaten. What other programs out there allow such mixing?

Re:Mathematica?

[Anonymous Coward]

Mathematica as a functional language has at least one glaring problem, however. That is, function calls become frames on the call stack. Hence there can be too much recursion for the stack, as opposed to too much recursion for RAM.

SML, Haskell, and Scheme do not have this problem.

I also am mystified with the interplay between Mathematica's typechecker and its evaluator.

I suppose Wolfram will just glue a couple of new features on to the language and declare it improved, anyway. Perhaps he will hack some logic programming capabilities onto it, as well (mock excitement).

OCaml software

[Richard W.M. Jones]

At my company we've been working on a range of software to make OCaml practical for web app writers. If you're used to Perl for development, you'll find mod_caml very familiar. And we have a DBI-like database layer. And for good measure you can reuse all your Perl code and libraries during the transition.

http://www.merjis.com/developers/

Rich.

Imperative JPEG

[William Tanksley]

Just thought I'd post a link to an example of an imperative language implementing JPEG decoding in only a few pages of code. :-).

-Billy

Anyone Know A Good Tutorial or Introduction?

[Abuzar]

I downloaded the book. However, at 160 pages it seems a little intimidating. I'm not a real programmer, I just code. What I had in mind was something akin to a 2 to 10 page (max) tutorial that would help me learn about it, and then I could apply it to my Perl code.

I did something like this before, there was a 2 page tutorial on the net that showed functional programming for perl. It showed you various techniques like passing functions into functions and making compound functions. Stuff like that has come in handy.

So, at the moment I've written stuff to generate user interfaces and databases given a description of how they should look like (using XML). I'm wondering how I can move beyond using arrays, hashes, and objects in Perl. The article sounds like there might be something that the Functional people have figured out about writing application logic and user interface Models (as in the M of MVC) that I can steal from. Is this true?

Re:Anyone Know A Good Tutorial or Introduction?

[Anonymous Coward]

a 2 to 10 page (max) tutorial that would help me learn about it, and then I could apply it to my Perl code.

ahaha...
you'll probably need to do more learning than that.

Let me also try to explain why FP is good

[Tom7]

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

Re:Let me also try to explain why FP is good

[andrew cooke]

i agree (that write once variables are a feature, not a bug), but it took me a long time to see that and i was trying to relate to how people who haven't used functional programming before might feel. i don't need to tell you it's good, but i think i do need to explain to people who haven't used a functional language that it is ok to find it odd at first (i certainly did).

Re:Let me also try to explain why FP is good

[pjt33]

Java does have polymorphism (and it's getting a more expressive type system - F-bounded parametric polymorphism). Let-polymorphism doesn't define polymorphism.

Also, while it doesn't have algebraic datatypes and pattern matching in the way SML does, you can get something very similar that using the Visitor pattern.

As for tuple and sum types - hardly difficult.

I agree that the functional style is nice, but just because it's more obviously done with a functional language isn't to say it can't be done with Java. Quite a bit of the util package I've written consists of functional classes, including some which deals with polymorphic higher-order functions.

Re:Let me also try to explain why FP is good

[Tom7]

You can do all stuff with any programming language, but it is really painful and verbose to do functional programming in Java. It's true that ML-style polymorphism is not the only kind, and, ok, Java now has some kinds of polymorphism, but its type system still really sucks!

Oh for god's sakes..

[bl8n8r]

If if had any merit, Microsoft would have already stolen it, or SCO would be suing Curry for IP infringement. Nice try - back to work people.

Re:Oh for god's sakes..

[Anonymous Coward]

Simon Peyton Jones is a Microsoft employee.

Re:Oh for god's sakes..

[sfogarty]

They have. F#.

The tyranny of suckage: why Ocaml is not popular

[nothings]

Or maybe people don't use Ocaml due to flaws in the language and flaws in the implementation.

Here's an example of each:

- (language) lame support for imperative programming -- no equivalent to 'break' for loops, and even no equivalent to 'return' to allow you to return a value from the middle of a loop. Of course, imperative programming isn't the emphasis of OCaml, but it means that that "benefit" of having imperative features available when you need them isn't really quite as strong as you might like
- (implementation) useless compiler errors -- numerous mistakes will give you the unadorned response "Syntax error", and because the language is so lacking in redundancy, mistakes can be syntactically valid for a long way, causing the syntax error to show up 20 lines later; similarly, typecheck errors themselves can be hard to decipher, since the compiler doesn't show you where the inferred types are coming from, leaving you to track them down on your own

I base this opinion on having used Ocaml twice, working with several other programmers on IFCP entries, and from occasionaly pair programming with my officemate, who is probably the only game developer in the world using Ocaml.

Crystal Reports

[emurphy42]

Yup, that's it.

Crystal Reports is also a sort of functional system (though I've abused the hell out of its imperative capabilities, mostly to make up for lack of programming tools at other levels).

correctness

[cabazorro]

I search the page for the word in it wasn't ther
so here it goes:
In the white paper I read about functional
languages there is a strong emphasis on coding
an algorighm and showing it's correctness or
proof. In today's arena we programmers gauge
ourselves by our abilities debugging code. Bugs
are a given. We like to believe that debugging
thousand lines of code is a small price to pay
for the wonders of procedural language.

Hard to quantify I must admit but for those who
compare Haskell or other functional language against
any procedural language please remember the
issue of correctness.
Because even if is cheaper and faster to count
cows by counting the legs and dividing them
by four...still wrong.

Just curious...

[Anonymous Coward]

Since c++ template metaprogramming seems to be the most widely used "functional programming language" in use today, wouldn't there be a market for re-writing many functional programming books using c++ template metaprogramming techniques. (Structure and Interpretation of Computer Programs, The Little Schemer, The Seasoned Schemer)? Any comments?

I, too, like any language

[BigFootApe]

that supports GOTOs. Of the computed sort.

As a functional programming fan

[twem2]

I'll have to check this out.

Anyone who wants to learn ML and the principles of functional programming could do a lot worse than getting a copy of Larry Paulson's "ML For The Working Programmer"

Re:The tyranny of momentum: why Ocaml is not popul

[Anonymous Coward]

There's a nice compendium of qualitative comparisons of O'Caml to other languages (Java/C/C++/Ruby/etc) here

The O of Erastothenes is just slightly supralinear

[Anonymous Coward]

O(n*log(log(n))) steps to find the primes out to n. If you want the first n primes, add in another factor of log(n) to account for the density of primes.

The sieving involves one action every time a prime divides a composite number (ie strike out that composite number). Since the average number of prime factors averages out to log(log(n)), the number of actions is just barely supralinear.

In reality, of course, if you don't want to accept artificial limits, you will hit the fact that just talking about very large numbers gets more difficult since the representation has to get larger than any convenient fixed size representation. Throw in another log(n) if your code handles large integers.

I don't know if any purely functional implementation can approach this performance level. The basic action of "striking out" involves modifying a value in place. Recopying the modified datastructure is problematic since the datastructure is large. Incrementally layering changes is likewise problematic since upon access you have to search your incremental changes - most of which do not apply to the number you are looking up.

Here are 2 implementations in Perl. One uses closures heavily (but isn't really functional since it uses assignment) while the other is very, very short. For amusement here is the short implementation (made longer by one space to avoid /. breaking a line in a bad place):

sub sieve {
grep{@_[map$a*$_,$_..@_/($a=$_)]=0if$_[$_]>1} @_=0..pop
}

print join " ", sieve(100);

It scales like the C version does, albeit with far worse constants. Other than practical memory issues, there are no limits on how big a list this can handle.

You are the troll and here is why!

[Anonymous Coward]

Dude. What you are writing is a troll itself.

Comp Sci is generally IS a programming degree. Computer Information System Degrees are a different branch of the I.T. sector.

Usually one can cross from either side if you have enough work exprience BUT for a MASTERS degree (in either) you take courses pertaining to the other side.

(e.g. Developers/Programmers "C.S." and System Admins/Network Admins "C.I.S.")

You're still wrong

[Anonymous Coward]

Until you define PRIME as the act of determining whether or not a given number is prime.

And by P in this case, we mean polynomial in the number of bits that you need to represent the number. In other words the standard solution of "trial division up to square-root n" is an exponential solution.

I wish you better luck the next time that you try to quote a result that you don't really remember and didn't understand.

Re:You're still wrong

[SparafucileMan]

PRIME is defined as determining whether a given number is prime.

Re:The tyranny of suckage: why Ocaml is not popula

[Anonymous Coward]

nothings wrote:
>
> lame support for imperative programming -- no equivalent to 'break' for loops,
> and even no equivalent to 'return' to allow you to return a value from the middle of a loop

This is false.
OCaml can raise exceptions, which will do exactly what you want.

> useless compiler errors -- numerous mistakes will give you the unadorned response "Syntax
> error"

Try running your code through the preprocessor (add "-pp camlp4o") and your "Syntax error" turns in to, for example:

File "foo.ml", line 8, characters 4-6:
Parse error: ':>' or ':' or ')' expected after [expr] (in [expr])
Preprocessor error
make: *** [foo.cmo] Error 2

I do wish people would take the trouble to actually learn the language before posting ignorant and derogatory criticisms like the one in this post. Your errors could easily have been corrected by reading the manual and/or looking through a FAQ. You're also welcome to ask questions on the OCaml mailing list, the OCaml Beginners Yahoo group, and #ocaml on freenode.

Cheers!

At least it's erm... exposed source??

[quinkin]

I don't do much on windows myself nowdays (if MFC and I never meet again, it will be too soon) but another dev mate gave up trying to figure out what the buggy control was meant to do and went and downloaded the leaked windows source.

So after literally WEEKS battling with this show-stopping bug, it took him a couple of hours to find the code, identify the bug and implement a work-around in his code...

Q.

Re:The tyranny of suckage: why Ocaml is not popula

[Anonymous Coward]

nothings wrote

mistakes can be syntactically valid for a long way, causing the syntax error to show up 20 lines later

This is virtually never a problem in practice. Syntax highlighting in your editor gets you 99% of the way there. And when I can't immediately see the source of a syntax error I simply hit "u", the undo key in vim and I can see what I did to cause the syntax error in the first place (usually an ommited semicolon). The Code a little... test a little methodology does wonders for this sort of thing, and any reasonably experienced programmer should be using it anyway.

OCaml b0rks on large data problems

[Anonymous Coward]

I only wish that I could use OCaml in my projects. Unfortunately, on 32-bit architectures (read: x86), OCaml native arrays can contain no more than 2^22 elements.

However, if you tend to work with arrays containing 10M elements or more, OCaml just is not an option. (BigArray is not an option unless your data are all numerical.)

Sadly, this restriction rules out the use of OCaml in large-data settings, i.e. most numerical and scientific computing.

Does SML have array size restrictions?

OCaml

[Anonymous Coward]

OCaml supports functional, imperative and object oriented paradigms, is much more widely used, and therefore has many more libraries and applications written in it and for it. No that Scala doesn't have potential, but if you're looking for something practical use OCaml.

Re:OCaml

[primus_sucks]

Scala can use any Java library, and eventually it will be able to use .Net libraries. I don't think OCaml has more libraries than Java and .Net combined! (Not that I think OCaml isn't a cool language, much better than C or C++ for native apps, IMO)

Re:OCaml

[Anonymous Coward]

OCaml can use C/C++ and Perl libraries. I think those easily give Java and .NET libs a run for their money.

Re:The tyranny of suckage: why Ocaml is not popula

[scrytch]

You forgot a couple more:

* Total lack of ad-hoc polymorphism. This language has such a problem with overloading, you need a different operator for adding floats than you do for adding ints.

* Supposedly awesome module functor calculus that fails to show up with any useful examples in the standard library -- for data structures, you tend to call a lot of static functions in modules that are, you guessed it, non-polymorphic.

* Lack of compiler warnings. My all time favorite error in ocaml goes like "The value is declared type Foo, but is used here with type Foo". It will drive you insane when developing via ocaml-mode in emacs, because it doesn't do a fresh recompile, so you end up redefining types and the compiler doesn't make a peep of warning. I learned to stick with makefiles when developing, to preserve my sanity.

As a better C, ocaml looks great. But it fails to offer many credible alternatives to what even ugly old C++ offers in ad-hoc and parametric polymorphism.

CS Journals

[perl-guy]

Genamics lists 989 journals related to Computer and Information Sciences. Surely some of them are good.

How about the Journal of Functional Programming or Theoretical Computer Science, or perhaps the Journal of Algorithms. And, for a more general approach, there's always the Journal of the ACM.

I haven't read any of these extensively, but surely some of them will have the kind of articles you'll enjoy.

Re:The tyranny of suckage: why Ocaml is not popula

[Anonymous Coward]

srytch wrote:
>
> Total lack of ad-hoc polymorphism. This language has such a problem with overloading,
> you need a different operator for adding floats than you do for adding ints.

This is a Good Thing (TM). That means that your language isn't going to do implicit conversions from floats to ints (or vice-versa) behind your back. This was an explicit design decision, due to the recognition that the programmer is smarter than the compiler. You are the programmer so you should decide how types are converted from one type to the other, not the compiler. Of course, if you want, and only if you want, you can easily create a composite type and a library of functions that will do all of the conversions for you. Curiously no one has seen the need to implement such a library.

> Lack of compiler warnings. My all time favorite error in ocaml goes like
> "The value is declared type Foo, but is used here with type Foo".

This is covered as the first question in the OCaml FAQ, and personally I have run in to that situation exactly once in my entire experience programming OCaml. So I consider this particular error message a relatively rare corner case... certainly nothing to condemn a whole language over.

> As a better C, ocaml looks great. But it fails to offer many credible alternatives to what
> even ugly old C++ offers in ad- hoc and parametric polymorphism.

Don't even get me started on C++. Instead, start by reading this. C++ is not even in the same league as your average functional programming language, much less OCaml.

Second, ocaml has parametric polymorphism. Read this. And this... google for more. And here's an example of OCaml's parametric polymorphism:

# let f x = x ;;
val f : 'a -> 'a = <fun>

This creates a parametrically polymorphic function, named "f". And here is how you would use it:

# f 3.14159 ;;
- : float = 3.14159
# f "0wn3d" ;;
- : string = "0wn3d"

Right, now compare that to what you wrote before

[Anonymous Coward]

Back here you said, PRIME (aka, finding all the primes) is not greater than n (aka, linear). Which made perfect sense in context since the sieve that was under discussion finds all of the primes.

However, as you agree just above, that isn't the definition of PRIME.

Which means that, in addition to getting the efficiency of the algorithm wrong, you got the definition of PRIME wrong.

A REQUEST FOR INFORMATION

[Anonymous Coward]

I'm an electrical engineer, so it's not surprising that there's a lot of computer science that I don't know about, but this is literally the first I have heard about functional programming, and suddenly all these people are replying saying they've read the book, or do such programming at work... I feel like I've missed something.

For you people who use this, or say it is used at your work: for what is it used, and why this versus any other language?

I use C/C++, Java, Perl, and various types of microcontroller assembly, and lately I've been wondering if I should learn Python or Ruby. Now here's another can of worms.

I have found that learning a computer language introduces me to new mental constructs, different ways of representing information that can often be applied outside of coding... so I guess what I really want to know is: what languages should I, as an engineer, know to be able to communicate effectively with programmers?

I realize the question is broad and open to interpretation, but if anyone has recommendations I would be most grateful.

Re:A REQUEST FOR INFORMATION

[j h woodyatt]

Scheme.

Seriously. It's easy to learn. You don't have to immerse yourself in it for hundreds of hours just to learn how the syntax and semantics of the language work. You can pick up the whole enchilada in a couple hours of fooling around with it.

Other functional languages might be preferable for specific applications, but Scheme is the one that I would recommend learning first. It has all the basic features you need for functional programming. Learn how Scheme coders write algorithms on sequences of values and you'll cover the most useful ground in the shortest time.

--

Re:A REQUEST FOR INFORMATION

[Sri Lumpa]

I will have to agree with the above poster that Scheme is probably the best language to learn functional programming.

A good introduction to Scheme is Scheme in fixnum days (google for it) it is quite simple to start with but also involves more esoteric example near the end which, while they are a bit harder to comprehend than most imperative algorithms at first give you a small epiphany when you finally grok them.

Re:The tyranny of suckage: why Ocaml is not popula

[Anonymous Coward]

This is a Good Thing (TM). That means that your language isn't going to do implicit conversions from floats to ints (or vice-versa) behind your back.

Ad-hoc polymorhism / overloading does not imply implicit conversions.

Believe it or not

[Anonymous Coward]

A bunch of the prominent people in the FP community work for Microsoft in England.

Ocaml vs. SML

[Trepidity]

Just out of curiosity, since I know and use SML but have only heard of Ocaml: what're the relative strengths? Is there a reason for me to learn Ocaml as well? I gather that they're both derived from the original ML, and share a lot of features, but I was wondering whether I ought to care about Ocaml or just stick with SML (since I already know it).

might depend on what areas you're considering

[Trepidity]

If you're looking for really earthshattering ideas that every computer scientist would know, like, say, the idea of reducibility to NP-complete problems, I'm not aware of any recent ones. But if you're willing to go for more narrowly-applicable ones, there's a bunch. There's been a few new transforms in the last five or so years that have been applied to audio compression, though many are just variants on older ones, so maybe aren't "really" new. Machine learning has a bunch of stuff as well: support vector machines were invented in 1998 I think, to pick one example.

The trouble with academics...

[Anonymous Brave Guy]

Can you prove that general sorting cannot be less than O(n log n)? This is fundamental. If you can't do it, you do not know computer science. (Flip side of coin: if you can, then you are at least heading the right direction).

Well, you might not be any good at complexity theory, but that's hardly the same thing. Computer science is a broad subject, and anyone who can tell me in 2004 that "computer science" is just a narrow mathematical specialisation is academic in every sense of the word.

(And yes, I do have an academic background in CS, and yes, I can prove the standard limit on sorting.)

A hobbyist tinkering in the garage does not a scientist make. Put out a publication comparing your methods with other known methods. Give theoretical upper and lower bounds on run time, memory usage, jitter, etc. Criticize yourself and explain the defects in your methods. Submit it to peer scrutiny. That's science.

No, that's academia, which is not at all the same thing.

Re:The tyranny of suckage: why Ocaml is not popula

[scrytch]

> This is a Good Thing (TM).

"Hey they're not warts, they're beauty marks". Funny how it becomes a Good Thing in one's Favorite Pet Language. I'm not talking about MIXING floats and ints, I'm talking about the fact that "1.0 + 2.0" is a syntax error in ocaml. You need "1.0 +. 2.0", because + will always and forever only handle ints. Well, unless the compiler makes some exceptions, but don't try this with your own operators, kids.

> # let f x = x ;;

Identity is polymorphic. Excuse me while I cheer. How about a function that computes something, because I do eventually have to degenerate to base types. Now there are polymorphic types as well, but you have to anticipate the types it may be and change it at the declaration of the type -- in other words, it's not inferable. Plus, the syntax of polymorphic types is an awesomely grungy wart, and can't begin to compare to type families.

I actually like ocaml, mind you. Unfortunately, it hasn't seen serious development around anything like smarter compiler feedback, let alone language features like type families. In fact, mentioning such a thing elicits so much negative advocacy, one gets the impression that the language definition has become Set In Stone For All Time Forever And Amen, and that only weird and crufty macro metaprogramming hacks in camlp4 will push the envelope any further.

Re:The tyranny of suckage: why Ocaml is not popula

[j h woodyatt]

Ad-hoc polymorhism / overloading does not imply implicit conversions.

Actually, the phrase 'ad-hoc' here is the killer.

What is the type of this function?

let f x y = x + y

It can't be this:

val f: 'a -> 'a -> 'a

...because then this would make no sense:

let n = f `Foo `Bar

There is an experimental extension to Ocaml (called Gcaml) that gives support for explicit overloading to the language. But that keeps it from being 'ad-hoc' now, doesn't it?

It would be nice to get 'generics' added to Ocaml and there appear to be some sound reasons for doing it, if the comments from the Caml team at INRIA are to be believed. However, it doesn't seem like there is any sound way to do it and still be 'ad-hoc' about it.

You're going to have to explicitly indicate all the specializations of an overloaded function or operator.

--

Re:The tyranny of suckage: why Ocaml is not popula

[Anonymous Coward]

> "Hey they're not warts, they're beauty marks". Funny how it becomes a
> Good Thing in one's Favorite Pet Language. I'm not talking about
> MIXING floats and ints, I'm talking about the fact that "1.0 + 2.0" is
> a syntax error in ocaml. You need "1.0 +. 2.0", because + will always
> and forever only handle ints. Well, unless the compiler makes some
> exceptions, but don't try this with your own operators, kids.

Ok, so you have to remember to type a period when you perform arithmetic
operations on floats. This is a minor annoyance at worst. It took me
all of maybe five minutes to get used to this when I started programming
OCaml. Syntax quibbles are about the most petty thing to focus on in
debating the merits of a language. OCaml gives me so much power that
I would gladly type an extra period after every keyword if that's what
it took in order to use it. Besides, the compiler will remind if you
forget, so it's not like you'd introduce a hidden bug in to your code
that will end up corrupting your data if you forget. So I really don't
see this as a big deal. Your milage may vary.

> Identity is polymorphic. Excuse me while I cheer. How about a function that computes
> something, because I do eventually have to degenerate to base types.

Well, you can build data structures using parametric polymorphism:

# let f x y = x::y ;;
val f : 'a -> 'a list -> 'a list =
# f 1 [2; 3] ;;
- : int list = [1; 2; 3]
# f "foo" ["bar"; "baz"] ;;
- : string list = ["foo"; "bar"; "baz"]

similarly:

# let f x y z = x,y,z ;;
val f : 'a -> 'b -> 'c -> 'a * 'b * 'c =
# f 1 2 3 ;;
- : int * int * int = (1, 2, 3)
# f "foo" "bar" "baz" ;;
- : string * string * string = ("foo", "bar", "baz")

> Plus, the syntax of polymorphic types is an awesomely grungy wart, and can't begin
> to compare to type families.

What is ugly about the parametrically polymorphic functions above? They seem quite elegant to me.

Re:The tyranny of suckage: why Ocaml is not popula

[renoX]

I'm not the one having made the original comment but, using exceptions for break or return?
Bleach, this is ugly!

Break and return have a purpose (changing the flow of execution), exceptions a different one (reporting error), mixing both is ugly.

What the point of using a "clean language" if you need to hack around the language?

Me I tried to learn Ocaml and didn't manage to do it..
Now I'm learning Ruby which is much more easy for my poor brain, and it is also the most readable language I know (unfortunately it is slow also).

Re: Sorting in < O(n log n)

[some guy I know]

If you are allowed to do bit-twiddling, and know that your objects are bounded in size, you can do better than n log n

True.
For example, if no two objects have the same value, and they are all integers in the range 0 to k, they can be sorted in O(n) by using an array of size k.