Joy of OCaml - Part I
Many programming problems lend themselves easily to solutions based on Functional Programming languages. It is not hard to convince ourselves of this after coding a Language like OCaml or Haskell.
This article does not explain the basics of OCaml. Nor is it too advanced. The functions are kept as simple as possible. This is the learner’s perspective after all.
Dr Xavier Leroy was awarded the Milner Award in 2016 for achivements including OCaml.
OPAM does not seem to install easily in Windows. As is my wont in such cases I started with Cygwin and after two days switched to a Ubuntu VM. I didn’t think I was gaining much by reporting Cygwin permission issues to owners of OPAM Windows installers.
The IDE is the venerable emacs. All diagrams are drawn using the Tex package, Tikz.
This function returns the index of the smallest element in an Array. It illustrates some of the various usages of let but this function uses imperative constructs and cannot be considered a real example of a OCaml function.
- let is used to define a function called min_index
- b holds a copy of the Array a before it is sorted because
- Array.sort does not return anything useful.
- let can also be used to define a variable
- i holds the value -1
- Since Array.iteri updates i, expects only unit. Obviously this is a side-effect and Functional paradigms are based on languages that generally do not mutate any state in a program. Read the next section.
The hardest concept to fathom is side-effect or mutation. OCaml is mostly a functional language but It has imperative constructs too and mutable data structures which I have decided to gloss over as my intention is to highlight the functional programming paradigm. But an example of imperative code is given at the end.
The OCaml code shown below does not mutate any value or data structure. It creates a new List. That is the hallmark of functional code. No side-effects unless we intend to create it using imperative constructs.
Composable functions can be combined to create higher-order functions. Let us assume we want part of a list and the rest to be dropped. We want to take n elements and drop the rest.
These two functions take ‘n’ elements from a list and drop ‘n’ elements. This is not the Idiomatic OCaml style I have come across because the algorithmic complexity is off the scale as the length of the list is computed repeatedly.
But these two functions can be composed to form other higher-order functions that operate on the lists obtained.
Let us assume we are working on lists of words to find out which word follows an n-gram. In this case we want to find out which word follows all sets of 2 words in a sentence. This is something like a Markov Chain.
We take 2 and drop the rest.
Now we slide the window to the right and drop the first element.
We slide the window to the right and thereby get the following word. Our composable functions can be used to figure out a simple Markov Chain.
The Option type
This obviates the need to litter code with checks for the presence or absence of an expected result.
‘Some value’ means that the value is found and ‘None’ means it isn’t.
Let us consider the store function shown above. We fold the Hashtbl and accumulate the count before returning it at the end. Fold is the functional style of operation on data structures.
If the key matches a value we accumulate the count in accum.
Fold has some semantics that originates in the deep bowels of the functional paradigm but we print some values to understand that. Unlike a fold on List which can be left or right, a fold on Hashtbl seems straightforward.
A rather contrived example of List.fold_left is
This is the result. We move from the left storing the previous value in old and the current value in cur. The check result=true short-circuits the logic in this simple example.
# issorted ["b";"c";"d";"a";"b"];; - : bool = false # issorted ["b";"c";"d";"a"];; - : bool = false # issorted ["b";"c";"d";"b"];; - : bool = false # issorted ["b";"c";"d"];; - : bool = true
The contrast here is between pure functional style of programming without mutating any state and the imperative features that operate based on side-effects.
This code checks if a List is sorted or not.
Even though OCaml has such constructs an aspiring functional programmer should be cautioned. It is all too easy to forget that we are learning about functions and hark back to an earlier style we are used to.
Let us write a more idiomatic OCaml function that does the same thing.
So based on some of the functions defined above we try to find the shortest-path. This is from chapter 24. of Introduction to Algorithms by Cormen et al.
So, for example, I represent this graph
A caveat is that this code is not as functional as I want it to be. There are far too many loops and imperative structures here.