Before we try to come up with a better solution for the problem in the previous post, let us look at another familiar problem - Quicksort. A quick refresher of mergesort from one of the earlier posts will make this exercise much simpler. In mergesort, we essentially wrote a split function to split an input list into two lists and recursively called the mergesort algorithm on each of the sub-lists produced by split and eventually merged them using a merge function that merges two lists by comparing the element at the head of the sub-lists.

The idea behind quicksort is similar. Instead of just splitting the list into two sub-lists, we are going to choose a pivot element (a fancy name for just an element from our input list) and split the list into two sub-lists in such a way that all the elements in the input list that are less than the pivot element would fall into one sub-list and the rest of the elements will fall into the other. Now that we are very much comfortable with writing recursive functions using accumulators, let us go ahead and write one for partitioning the list into a pair of lists (two sub-lists) given a pivot element. So, the inputs to our function are a list lst (to split) and a pivot element.

let partition pivot lst =
  let rec aux (acc1, acc2) l =
    match l with
    | [] -> (acc1, acc2)
    | h::t -> 
      if (h < pivot) then aux (h::acc1, acc2) t
      else aux (acc1, h::acc2) t
  in
  aux ([], []) lst;;

Let’s go ahead and see what it does on a sample list lst1 which contains [1; 11; 9; 3; 6; 7; 2; 29]. Let’s pick 7 to be our pivot element.

let lst1 = [1;11;9;3;6;7;2;29];;
partition 7 lst1;;
(* - : int list * int list = ([2; 6; 3; 1], [29; 7; 9; 11]) *)

As we see, all the elements less than our pivot element, 7 in this case, are in one of the sub-lists generated by partition function.

Now, quicksort is just choosing the head element as the pivot, generating two sub-lists l1 and l2 and calling quicksort recursively on each of the sub-lists. Since each recursive call pushes the smaller element further towards the left, eventually when all recursive calls return, the list would be sorted in acsending order.

let rec quicksort lst =
  match lst with
   | [] -> []
   | x::[] -> [x]
   | h::t -> let l1, l2 = partition h t in
     quicksort l1 @ (h::quicksort l2);;

And let us try it on lst1:

quicksort lst1;;
(* - : int list = [1; 2; 3; 6; 7; 9; 11; 29] *)

This exercise will help us find a better solution to the problem of finding the minimum missing natural number from an unsorted list. Does this ring any bell?

Let’s write a program to find the minimum missing natural number. We would be given an unsorted list of natural numbers, say [0;3;2;9;1;7;5] and we need to return 4. Let’s assume that there are no duplicates. And if we provide a list that does not start with 0 (natural numbers start with 0 and we assume that we provide proper input), we just return 0 as it is the smallest natural number.

How do we go about solving this problem. Once we look at unsorted, we can think of sorting the provided list first. Once we sort the list, we just need to go through the elements of the list one by one and find the missing number. As we have sorted the list already, the first missing number we encounter would be the minimum missing number.

let min_missing_num lst = 
  let sort_lst = List.sort compare lst in
  let rec find_min sort_lst = 
    match sort_lst with
    | [] -> -1
    | x::[] -> x+1
    | x::y::_ when y - x > 1 -> x+1
    | _::tl -> find_min tl
  in
  find_min ((-1)::sort_lst);;

Here, we are using OCaml List module’s sort function that has the following signature:

(* - : ('a -> 'a -> int) -> 'a list -> 'a list = <fun> *)

And compare is a comparision function that has the following signature:

(* - : 'a -> 'a -> int = <fun> *)

Essentially, compare x y returns 0 if x and y are equal, -1 if x < y and 1 if x > y.

Can we do better than this algorithm for finding the minimum missing natural number? Hint: sorting the input list is not very cheap - we could avoid that.

Just happened to listen (again) to a TED Radio hour podcast on success. Although I don’t quite agree with the fragment about dirty jobs, some part of the podcast is worth listening to. Most people end up doing dirty jobs because they were less fortunate to get the kind of life the many of us were fortunate enough to get - education, encouraging family, help, opportunities, etc. To some extent, some of them continue doing dirty jobs also because we let them down as a society. We should continuously look to empower the less fortunate around us, in whatever way we can - one of the easiest is to share information and knowledge. Here’s the full podcast:

In one of the previous posts we looked at a recursive function explode to explode a string into a list of characters. Now, we shall try to implode a list of characters back into a string. We’ll call this function implode that takes a list lst as input.

We need an accumulator in order to collect the characters from the input list to prepare our output, so let’s create one acc whose length would be equal to the length of the input list lst (of characters).

1. Base case - if the input list lst is an empty one, just return the accumulator.
2. If the list is not empty, we pick the head element and push it into the accumulator. We start with index '0' of the (mutable) String and recursively call the function on the remaining part of the list, incrementing the index for each call.

let implode lst =
  let acc = Bytes.create (List.length lst) in
  let rec aux i l =
    match l with
    | [] -> acc
    | h::t -> Bytes.set acc i h; aux (i + 1) t in
  aux 0 lst;;

Note: The latest version of OCaml, my preferred programming language, has a mutable data-type Bytes while it made the String data-type immutable.

Food for thought - how would be implement implode using the immutable String type, in a purely functional fashion?

In our previous post we saw how to check if a given number is prime. Now, what if we want to find all the primes from 1 to 1000? Sure, we can call our is_prime() function on every number from 1 to 1000 and list out the ones that pass the test. Is there a better way? There absolutely is! And it turns out that it was invented by a Greek mathematician Etatosthenes, who by the way also happened to invent Geography. The algorithm is commonly referred to as Sieve of Eratosthenes.

We start by assuming that all the numbers, say 1 to n are primes. Assume we have an array of size n and we marked all the elements as prime. Now, we traverse the array and start marking out all the multiples, say 2, 4 ,6, 8, 10, ... as not prime, and similarly 3, 9, 15,.... Once we are done, we are left only with primes. I am still amazed at the simplicity of this algorithm given that it was invented more than a couple of thousand years ago.

vector<int> eratosthenes(int n) {
  vector<int> result;
  vector<bool> prime(n+1, true);
  prime[0] = false;
  prime[1] = false;
  int m = (int)sqrt((double)n);
  for (int i = 2; i <= m; i++) {
    if (fast_is_prime(i))
      result.push_back(i);
        for (int k = i*i; k <= n; k += i) {
          prime[k] = false;
        }
  }
  return result;
}

That’s all folks!