How long does it take for you to be comfortable with Haskell?

Question

I'm an OK C/C++ programmer. I find Haskell very intriguing. But it seems to me, that although it's relatively easy to write clean Haskell code, as it mimics math (which I'm very comfortable with) pretty well. It's very hard to write clean code in Haskell that runs fast.

A faster version of quicksort of Haskell is very long and scary, which has no resemblance to the naive but short (two lines), clean and intuitive implementation. The long and scary version of Haskell is actually still much slower than the shorter and simple C counter part.

Is it because the current Haskell compiler is too dumb or it's just impossible for mortals (other than SJP of course) to write fast Haskell code?

Answer 1

There is a very specific reason why quicksort ain't so quick in Haskell. It is a God-like example of an algorithm that has brilliant hackery woven into how it works - what I mean by hackery in this case is the kind of techniques that a true Haskell devotee would regard as unnecessarily dangerous and non-mathematical. The original implementation made every effort to break the rules that Haskell imposes on itself: the genuine quicksort works by overwriting storage slots with new information. This is very painful to do in Haskell, which finds it much easier to make whole new copies of existing information.

So although that naive two line Haskell version captures something of the essence of quicksort (it does the same number of key comparisons), it isn't really quicksort. It's missing a large portion of the genius that went into it, which took full advantage of the ability to tweak the state of existing values. So it makes large numbers of intermediate copies of pieces of the list.

Speculation: could a Haskell compiler analyze your code, applying the same reasoning as Hoare (inventor of quicksort) and figure out that it could optimize it by completely reimplementing it in a stateful way? Possibly.

Answer 2

The reason is that mathematical foundation of computers is different from mathematical foundation of Haskell and functional languages in general.

To get taste of problems compiler is facing... Translate Haskell program to C, keeping it as close to original as possible, then try to optimize that C code (without rewriting it from scratch in C-way)

It's not dumb, but functional languages are not made for performance, and concise mathematically simple notation doesn't come for free.

Answer 3

The point is not to write fast Haskell code, but to write Haskell code fast. When you get there and you need to make your code fast(er), start optimizing (or use the FFI, you don't have to forget your C++ skills). In Haskell you are looking for elegance, reliability and maintainability first. I'd add profiling to my Haskell-fu, so you don't waste time optimizing that which is not used. And remember not to optimize prematurely.

Answer 4

So, to answer the question in the title, you will likely feel fairly at home with the basics of Haskell within a short time. Especially if you're already familiar with functional programming. The things that really make Haskell stand out, such as laziness, type classes, type families, and of course the dreaded monads (and arrows) are likely to require more time to understand and get used to. There are good resources for learning the language, many freely available, together with a helpful community, so I'd say you'd likely be well on your way to feeling comfortable within a week or two of semi-serious study ;-)

I think it's worth it though, just like some people argue that it's worth learning Lisp even if you'll never actually use it for anything. It's worth it because it makes you a better programmer--it makes you think differently. I'd argue Haskell has a similar effect.

Answer 5

You ask two different questions: learning and performance.

• It took me about a month to become comfortable with functional programming using recursion, pattern matching, map, filter, and fold. I did all that with ML but it translated to Haskell very easily.
• It took me two or three years to wrap my head around monads, but that's because I read the wrong stuff. I think there are better tutorials now. But if you're beginning, avoid monads for a while.
• It took me several months to get good at creating new type classes, but using the existing ones was easy.
• I'm still not sure I have the hang of lazy evaluation. But I love Haskell's purity and tend to treat lazy evaluation as an unhappy accident that only a few people (like John Hughes) know how to exploit.

You've observed a performance problem only because you've adapted an algorithm loaded with mutation, which Tony Hoare designed for imperative languages, and tried to translate into Haskell. In Haskell as in any other functional language the expensive operation is allocation. Try writing a merge sort and you'll find it's simple and performs very well.

How do you avoid making similar mistakes in the future? Have a look at Chris Okasaki's book Purely Functional Data Structures. Great book, and it will help you learn the 'functional way of doing things' without giving up performance.