Wednesday, 24 October 2007

Balanced binary search trees

The OCaml Journal just published an article describing why balanced trees are so important in functional programming languages and how they can be implemented easily and efficiently in OCaml:

"Immutable data structures are a core concept in functional programming and balanced binary trees are the single most important such data structure. The OCaml programming language allows balanced binary tree implementations to be written clearly and efficiently. This article describes the design and implementation of a basic balanced binary search tree data structure similar to that of the built-in Set module..."

To read this article and more, subscribe to The OCaml Journal today!

Saturday, 13 October 2007

Implementing the FFT in OCaml

The OCaml Journal just published an article describing a simple but efficient implementation of the Fast Fourier Transform:

"Writing an implementation of the Fourier transform is an excellent lesson in algorithm design and optimization. Moreover, the Fourier transform is one of the most essential tools in numerical computing, with applications ranging from spectral analysis in science to the multiplication of large integers in mathematics. This article describes the design, implementation and optimization of a high-performance FFT implementation in OCaml..."

To read this article and more, subscribe to The OCaml Journal today!

Tuesday, 2 October 2007

What do you take with you when police are banging on your door at 4am and telling you to exit the building?

Joel Reymont posted the following review of OCaml for Scientists in August 2006 that was since lost in the aether:

"Objective CAML for Scientists August 23rd, 2006

There’s a trash compartment a few meters in front of our windows and down a few steps of stairs. It’s a small pass-through room of sorts with exit to the street. It houses a few large wheeled garbage bins and it also happens to be right next to the electrical room housing the transformer for our urbanization.

There was a huge fire in the garbage room about 4am today and there, apparently, was a dead body. I’ll try to take and post some pictures later to help you visualize what I’m talking about.

What do you take with you when police are banging on your door at 4am and telling you to exit the building? Why, of course passports, bank cards, cell phone, my wife’s 15” PowerBook G4, my 17” MacBook Pro, a pair of Nintendo DS Lites plus cartridges. Also The Tipping Point by Malcolm Gladwell, All Marketers are Liars by Seth Godin and, here’s the kicker, Objective CAML for Scientists by Jon Harrop of the Flying Frog Consultancy.

This is a self-published book that cost me about 130 euro and it’s also one of the best, if not the best, OCaml tutorials around. The book consists of 260 spiral-bound pages printed on a good ink-jet or color laser printer. All the code examples are colored according to syntax.

The book follows a logical path through introduction to OCaml (syntax, types, pattern-matching, etc.), program structure, data structures, visualization, optimization, libraries, examples and advanced topics. The coverage is encompassing and the writing is clear.

I particularly like the chapters on visualization with OpenGL (very useful) and optimization. I haven’t seen such a thorough treatment of optimization in any other OCaml tutorials. I wish there was more material on improving cache coherency, though.

Overall, the book is pricey but unique or I wouldn’t have taken it with my passports!"