Answers to FP Koans, in OCaml

Since you can find published answers to the classic koans of Zen Buddhism, I also present answers to these FP Koans. Of course, if you read the answers before you come to understand the koan on your own, then as in Buddhism, you will cheat yourself out of joy of the experience of enlightenment :) The same goes for learning anything, it is far more rewarding to do it on your own than to be told the answer. And that, of course, provides an excellent segue-way into the first koan ...

The Koan of Imperative/Declarative

This one is easy. OCaml is a declarative language, and shares the property of other declarative languages that instead of telling the language the exact steps to solve a problem, instead you give a declaration of the problem at a higher level, and the language makes some decisions on the implementation for you.

In this koan, the poor student was demanding to be told how to achieve knowledge of FP, but Xavier's response is intended to remind the student that not only will he achieve knowledge of FP by learning to program in a declarative manner, but also that when learning, a student benefits more from being guided as what to learn rather than just being given the answers. And on a third level, perhaps you noticed that the student's demand is an "imperative" sentence, while Xavier's response is a "declarative" sentence :)

Perhaps the canonical example for declarative style in FP languages is the quicksort function, and here it is for integers in 2 lines of OCaml:

  let rec qsort = function
    [] -> [] | h::t -> qsort(filter((>) h) t) @ [h] @ qsort(filter((<=) h) t);;

Of course, I was trying to be terse for the purpose of illustrating the expressive power, so here is the same function, written to be a little more readable:

  let rec qsort = function
      []   -> []
    | head::tail ->
        let lesser  = qsort (filter  ((>) head) tail)
        and greater = qsort (filter ((<=) head) tail) in
        lesser @ [h] @ greater;;

[Note this may not be the fastest way to write quicksort in OCaml, but the intent is to illustrate the power of being able to express solutions declaratively.]

Now, if you appreciate that demonstration even in some small way, I have to admit that I exaggerated a little in the first paragraph. Declarative languages, just like imperative languages, do tell how to solve problems. However, the manner in which a solution is expressed may read more naturally if expressed recursively, and FP languages excel at executing recursive solutions efficiently.

The Koan of Currying (A koan about food, that is not about food)

As some of you may agree, curry is delicious food. However, this koan is not really about food. In this case currying refers to the form in which you write the arguments to a function, and is named after the late mathematician, Haskell Brooks Curry. Perhaps you have heard of another fine FP language: Haskell?

A student new to FP whose experience is mainly with imperative languages may not appreciate the value of writing functions in curried form. So I will tell you: it's all about partial application. And since partial application is one of things I love the most about FP and OCaml, I will take a moment of your time to illustrate in more detail.

Here is a function in uncurried form:

let eat (dinner, dessert) = appetite dinner; appetite dessert;;

Here is the function in curried form:

let eat dinner dessert = appetite dinner; appetite dessert;;

Now, in the uncurried case you will only be able to apply your function eat in a place that provides dinner and desert together (when things are grouped together like this, it is called a tuple, in fact). But in the curried case, you can partially apply your eat function in one place that provides dinner, and go on to some other place that provides dessert to fill the remainder of your appetite.

Another way to look at it is this: eat dinner -> eat'; eat' dessert -> result. In other words, with currying, after you give the first argument to your function, it returns a new function that can now be applied to the next argument. I think that as you learn FP, you will find that partial application can greatly help you in simplifying and refactoring your code. Of course, partial application is possible in FP languages, because FP languages all support Higher Order Functions (HOFs), which we will discuss in the next koan.

The Koan of HOF

Higher Order Functions (HOFs) are what functional programming is all about! In FP languages, you can create new functions and pass them to other functions. Aside from using partially applied functions, as mentioned above, one of the canonical examples of HOFs in FP is the ability to compose functions to create new functions. Here is an example directly from the fine tutuorial that is included in the OCaml documentation:

# let compose f g = fun x -> f(g(x));;

val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>

# let square x = x *. x;;

val square : float -> float = <fun>

# let cos2 = compose square cos;;

val cos2 : float -> float = <fun>

The Koan of Side Effects

The enlightenment that Daniel helped the student achieve was this: If you do not learn to program without side-effects, you will not learn when to program with side-effects. Some functional languages, like Haskell are functionally pure, and do not offer any imperative features. However, OCaml (and ML) provides a mixed paradigm where you can program in both declarative and imperative styles, because sometimes it is convenient to do so. Once you have achieved mastery, you will know when it is appropriate to take advantage of that convenience.

If you are coming to FP from an imperative background you should remember that now you need to learn to think and do things a little differently than before. Until you feel comfortable doing so, it's best to avoid your old habits altogether, if possible.

The Koan of Lazy Evaluation

Okay, so this is a really a joke that I was told second-hand, or third-hand. In Eager style a function might generate a list of values over which the caller can iterate, whereas in Lazy style, the caller invokes the function every time it needs a new value in the sequence. The Lazy function acts a generator, and in many cases you can think of it as generating an infinite stream of values. [OCaml is naturally an Eager FP language, but it does offer Lazy Streams and an explicit method of Lazy Eval by using the Lazy module. For more detail, I have written a Note on Lazy Eval].

So in this koan, Michel is the teaching function and he produces learning in the students when they query him :-)

The Koan of Static Type Safety

In this koan, we illustrate that OCaml is a statically typed language, which is a feature greatly appreciated by Markus, and so he tries to produce enlightenment in his friend, the disciple of dynamic typing. In a statically typed language such as OCaml, you will never make the error of applying a function to a value that has the wrong type, because OCaml won't let you do that. Now, in real life, people make such mistakes too, which is why at fuel stations, the nozzle of the diesel pump is of a different diameter than the nozzle of the petrol pump. So you may think that this koan may not be realistic, but in fact, since Markus has also used C in the past, he knew that he could easily put the diesel in the car with the help of a cast (a funnel :-).

By the way, if you do happen to put diesel in a gasoline car, the car will stop running, of course, but it will not ruin the engine. However, you will probably need to pay dearly to have a mechanic flush it completely out.

  • Last modified: Sunday, 10-Feb-2002 10:51:51 CST
  • Copyright © 2002 by Doug Bagley [Email]
  • [Home]