Programming and thinking the functional way

It made me think that recursion, no matter how short the code looked, was terrible.

Now I realize that recursion, thought about properly, requires so much less mental overhead. All those lines of code that vanished were really whole concepts and ideas which could vanish as well.

Of late, my style has been refined by working with theorem provers which make the ultimate connection. Recursion is absolutely nothing more than mathematical induction. Each recursive call is just you invoking the inductive hypothesis.

What that connection really drives home is that when writing a recursive definition you need to do so very few things. First, you need to make sure your definition has a good foundation—you must list all of the conditions where it terminates and ensure that they truly found and support the algorithm/proof. Then you must write the inductive engine that will burn away whatever inputs you receive down to the foundation you just made.

The release is in noticing that those inductive engines can be primed on the very tiniest actions—and those tiny actions are all you, the implementer, are responsible for.

When writing your inductive step consider only the things that are novel about this case. If I'm working with an input list and inducting on `cons` then all I must do is consider what happens to the head and tail of the list. Everything else will be handled by the turning of the inductive engine.

Now a good algorithm just feels like someone walked me into a room with a gigantic domino structure. I walk around it slowly and determine the ends and then just flick the single domino which will churn away inevitably the rest of the algorithm.

It is at the core of many mobile to internet gateways out there. At the core of WhatsApp. Some databases (Riak, CouchDB) and message queues (RabbitMQ).

Language-wise, besides concurrency constructs, you get pattern matching, immutable data structures (and bindings). Unlike Haskell, all types are dynamic (but strong).

Also a counterpart to Learn You A Haskell For Great Good is Learn You Some Erlang For Great Good:

http://learnyousomeerlang.com/syntax-in-functions#pattern-ma...

For example the quicksort sample would look like:

    sort([Pivot|T]) ->
      sort([ X || X <- T, X < Pivot]) ++
      [Pivot] ++
      sort([ X || X <- T, X >= Pivot]);

    sort([]) -> [].

1) If it's simple to imagine the computer doing something, it should be easy to program.

2) If it's simple to analyze something mathematically, it should be easy to program.

The first path leads to C-style programming with pointers and loops. The second path leads to lazy pure functional programming and beyond.

Personally, I'm in the first camp. Small functional programs are often shorter and more beautiful than their imperative and OO counterparts, but large functional programs quickly accumulate so many abstractions that they become incomprehensible to me, more so than large imperative or OO programs.

Maybe that just says something about my intelligence, or maybe the functional camp hasn't yet figured out how to write large programs in a readable way. Case in point, see the list of operators defined by the popular Lens library in Haskell: http://hackage.haskell.org/package/lens-3.8.5/docs/Control-L...

  public class QS {
  	public List<T> Quicksort<T>(List<T> l, Comparator<T> comp) {
  		if (l.size() <= 1) {
  			return l;
  		}
  		
  		List<T> lesser = new ArrayList<T>();
  		List<T> greater = new ArrayList<T>();
  		
  		T pivot = l.get(0);
  		
  		for (T t: l) {
  			if (comp.compare(pivot, t) <= 0) {
  				lesser.add(t);
  			} else {
  				greater.add(t);
  			}
  		}
  		
  		List<T> out = new ArrayList<T>();
  		out.addAll(Quicksort(lesser));
  		out.addAll(Quicksort(greater));
  		
  		return out;
  	}
  }

I don't think this is a fair comment considering the in-place Haskell implementation isn't incredibly readable either.

    main = let nan = 0.0 / 0.0 in
            do putStrLn $ show $ quicksort [nan, 1.0, 2.0, 3.0]
               putStrLn $ show $ quicksort [1.0, nan]


    [NaN]
    [1.0]

Haskell is elegant & Java isn't, but cherry picking examples always comes with a risk of making your argumentation straw-man-ish.

Would be interesting to see some examples where imperative isn't so horrible, and how Haskell compares. The in-place sort the author mentions, for example.

The good:

1) The definition of the algorithm is clear. It shows "how quicksort works."

2) It's trivial to see (and prove) that the function will terminate, and almost as trivial to prove that it will result in a sorted list. So, it is easy to show correctness.

3) The polymorphism makes this an easily reusable function right out of the box.

The bad:

1) That implementation is very inefficient. At a glance I think it would be O(n^2) time. (Edit: this is misleading, because it's only O(n^2) in the same way that quicksort is always O(n^2). It is inefficient in terms of memory usage, though. And possibly other ways; for instance, I'm not sure how laziness would affect this. But I don't want to be spreading FUD...)

2) The "efficient" implementation given at the bottom is just as inscrutable as any other quicksort implementation I've seen. More so because of the monadic code, single-letter variables (pr?) and opaque library function calls (unsafePartition?) being made. And I'm not even sure that it would work on a list, although since V.Vector appears to be a type class, perhaps list is an instance of it.

3) Both the efficient and inefficient implementations are concise in large part because of their use of library functions. This is often a good thing: Haskell provides a great way to abstract things because of its parametric and ad-hoc polymorphism, and allows for a lot of reusable code. But it comes at a cost too, which is that the actual instructions you're giving to the machine are very far removed from what the computer is doing. Who knows how much code is actually executed, how deep the rabbit hole goes, to translate those beautiful 4 lines into actual machine instructions? With Java, it's precisely visible what the machine is doing to execute your code. This is much less the case with Haskell.

I suppose you could say (broadly) that functional languages excel at expressing what your program should do, while imperative languages excel at expressing how your program should do it. There are cases when you care more about the former, and cases when you care more about the latter. The reason I take issue with the quicksort example, is that list-sorting is a case where you definitely care more about the how than the what.

-------------------

EDIT, since two people called me out on it: It was an overstatement on my part to say that it's "precisely visible" what your Java code will translate to, but to suggest the two languages have the same degree of abstraction from the CPU is ridiculous. The code translation from Java to bytecode is quite straightforward, because most of the optimization occurs at runtime with JIT. There is a reasonably direct relationship between the code you write, the bytecode it gets translated into, and the instructions executed at runtime. At the end of the day, Java code consists of a series of instructions for the computer to follow, while on the other hand in Haskell, you aren't even technically giving instructions at all -- you're just writing equations. Compiled Haskell code is completely inscrutable.

Also, I should note that I am an enthusiastic Haskell hobbyist, and write it on almost a daily basis. Although I might not come across it here, I am a huge fan of the language; outside of the languages I use at work, by far the one I use most is haskell.

Also for any C# peeps who already have had experiences using lambda expressions on the awesome .net platform. How was performance there?

http://fsharpforfunandprofit.com/posts/fvsc-quicksort

Beware, beware.