Let’s continue with tail recursion and folding (recollect our previous post. Let’s use those concepts to write insertion sort algorithm. In an earlier post we wrote a recursive implementation of insertion sort algorithm as below:

let rec insert x lst =
  match lst with
  | [] -> [x]
  | h::t ->
     if (x <= h) then x::h::t
     else h::(insert x t);;

let rec isort lst =
  match lst with
  | [] -> []
  | [x] -> [x]
  | h::t -> insert h (isort t)

Now, let’s write a tail recursive version of insertion sort. Let’s just call it tr_isort.

let tr_isort lst =
  let rec aux lst acc =
    match lst with
    | [] -> acc
    | h::t -> aux t (insert h acc)
  in
  aux lst [];;

Food for thought - is it possible to write a tail-recursive version of insert function that we used above? If yes, why don’t we try it. If no, why not?

So, how about reversing a list using our leftee function from our previous post?

Let’s work it out now. Here’s the original tail recursive function for your reference:

let tr_lst_rev lst =
  let rec aux_lst_rev lst acc =
    match lst with
    | [] -> acc
    | h::t -> aux_lst_rev t (h::acc)
  in
  aux_lst_rev lst [];;

All you need to observe is how the accumulator acc changes - here we take a list element we are currently processing and stick it before (at the head) of the current accumulator acc.

let tr_lst_rev lst = leftee (fun a x -> x::a) [] lst;; 

In most functional programming languages our leftee is actually called fold_left and is tail recursive. There’s also a fold_right which is not tail recursive, because of the way it applies the function to the list elements. More on this in a later post!

In an earlier posts, tail recursions were introduced using two very simple functions tr_lst_sum and tr_lst_rev. In this post, let us carefully observe the structure of some simple tail recursive functions and see what they have in common. We will understand and use this information to write a generic function that can be used to write these other functions. Sounds like inception movie eh? Let’s get started!

Here’s the tail recursive version of lst_sum to sum an input list lst of elements.

let tr_lst_sum lst =
  let rec aux_lst_sum lst acc =
    match lst with
    | [] -> acc
    | h::t -> aux_lst_sum t (acc + h)
  in
  aux_lst_sum lst 0;;

And here’s the tail recursive version of lst_len to compute the length of an input list lst of elements.

let tr_lst_len lst =
  let rec aux_lst_len lst acc =
    match lst with
    | [] -> acc
    | h::t -> aux_lst_len t (acc + 1)
  in
  aux_lst_len lst 0;;

Let’s carefully observe the above two functions and try to understand the pattern - the recipe for such a computation. In both the functions,

1. We have an initial accumulator (in this case the value is 0 but it could be anything in general)
2. We traverse the list, apply the auxiliary function to the initial value of the accumulator and a list element and compute a new value for the accumulator. 2.1. We do the above step to each element of the list (by calling the auxiliary function recursively/repeatedly on each element) and compute new values for the accumulator on the way
3. When we are done with the entire list, we return the accumulator contents as the result

Now, if we just denote the auxiliary function by faux, it has a general shape - faux acc lst - we do traverse the list lst, but this is the general shape that we observe - call faux on the initial value of the accumulator acc and a list element and use the resulting value as the new value of the accumulator for the next call. For example, in the above functions the new values of the accumulators are (acc + h) and (acc + 1). Now, let’s try to wrap this all into a single function, which we would call a leftee - which would take three parameters - an accumulator acc, a function f to apply (to the accumulator and list element), and of course a list lst to work on and will look like leftee f acc lst. We call it leftee for a reason… (I think readers are already getting a hint as to where this is headed. Good!).

let rec leftee f acc lst =
  match lst with
  | [] -> acc
  | h::t -> leftee f (f acc h) t;;
(* ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun> *)

As we see above the new value of the accumulator is the function applied to the current value of the accumulator acc and a list element h.

Now, let’s rewrite tr_lst_sum and tr_lst_len using our leftee:

let tr_lst_sum lst = leftee ( + ) 0 lst;;

Here ( + ) is the function - just the addition operator. Isn’t it super concise? Aren’t you in love with this already?

let tr_lst_len lst = leftee (fun x _ -> x + 1) 0 lst;;

Food for thought - how would you use leftee to reverse an input list?

Lately, I have been thinking a lot about my work - my daily job. Most of us have one, where we slog every day, working late into the night or all night. We may have complaints, dissatisfactions, pleasant and unpleasant experiences, awesome career growths or non-existence of such a thing, lots of learning or nothing at all, great colleagues, teams, workplace issues, and the list goes on. I listened to an interesting podcast on “Meaning of work” from TED Radio Hour several months ago and listened to it once again over this weekend.

Whatever your situation is, this is a great podcast to listen to. And if you’re a manager, there are important lessons for you too, if you are someone willing to listen and learn.

Let’s look at a couple of more examples in order to get us thinking towards using auxiliary functions and accumulators while writing recursive functions. This would help us write tail-recursive functions which are safer and always a good practice. Note that some of the language compilers do not optimize tail recursions and so be aware of this fact in order not to be surprised when you do not see performance improvements while using tail recursive functions.

Let’s write the standard explode function explode that explodes a string into a list of characters. i.e., if you pass the string "hello", it would explode it and return the list ['h'; 'e'; 'l'; 'l'; 'o'].

let explode s =
  let rec aux_expl n acc =
    if n < 0 then acc
    else aux_expl (n-1) (s.[n]::acc)
  in
  aux_expl (String.length s - 1) [];;

Let’s write another function prime_factors that would return all the prime factors of an input number n. Again, we shall use an auxiliary function to do the intermediate computations.

let prime_factors n =
  let rec aux_factors d n =
    if n <= 1 then []
    else if (n mod d = 0) then d::(aux_factors d (n/d))
    else aux_factors (d+1) n
  in
  aux_factors 2 n;;

That’s all for today! Hope it was enjoyable.