Using helper functions

Sometimes the list function we are trying to implement isn’t trivial to com-pute, even given the value of the recursive call. An example of such a

function is ^prefixes, which is like the ^suffixes example above, but in-stead calculates the list of prefixes of the input list. For example, we want to have:

prefixes [1;2;3]=⇒[[]; [1]; [1;2]; [1;2;3]]

Why is this not so direct to implement as^suffixeswas? Suppose we’re trying to calculate prefixes [1;2;3]. Following the structural recursion pattern, we would expect to call^prefixeson the tail of this list, which is:

prefixes [2;3]=⇒[[]; [2]; [2;3]]

Given this result for the recursive call to prefixes, and the head ¹, we need to compute^prefixesfor the entire list^[1;2;3]. Looking for a pattern, it seems that we need to put¹at the head of each of the prefixes of^[2;3]. Since this functionality isn’t given to us directly by prefixes, we need to define an auxiliary function to help out. Let’s call it^prepend. As usual, we document our examples as test cases.

(* put x on the front of each list in l *)

let rec prepend (l:int list list) (x:int) : int list list = begin match l with

| [] -> []

| ll:rest -> (x::ll)::(prepend rest x) end

let test () : bool =

(prepend [[]; [2]; [2;3]] 1) = [[1]; [1;2]; [1;2;3]]

;; run_test "prepend "[[]; [2]; [2;3]]" test

Now, using^prepend, it becomes much simpler to define^prefixes:

let rec prefixes (l:int list) : int list list = begin match l with

| [] -> [[]]

| h::tl -> []::(prepend (prefixes tl) h) end

let test () : bool =

(prefixes [1;2;3]) = [[]; [1]; [1;2]; [1;2;3]]

;; run_test "prefixes [1;2;3]" test

For another example where a helper function is needed, consider try-ing to compute a function^rotationsthat, given a list of integers, computes the list of all “circular rotations” of that list. For example:

rotations [1;2;3;4]=⇒[[1;2;3;4]; [2;3;4;1]; [3;4;1;2]; [4;1;2;3]]. Here again, thinking about how^rotationswould work on the result of

a recursive call illustrates why there might be a need for a helper function.

When we use^rotationson the tail of the list^[1;2;3;4], we get:

rotations [2;3;4]=⇒[2;3;4]; [3;4;2]; [4;2;3]

The relationship betweenrotations [2;3;4]androtations [1;2;3;4]

seems very nontrivial—it seems like we have to intersperse the head¹at various points (in the last spot, the second-to-last spot, the third-to-last spot, etc.) in the prefixes of the tail. We could perhaps write an auxiliary function that does this, but that still seems complicated.

Here’s another approach that simplifies the solution. Consider what information from the original list that we have at each recursive call to some function^f

f [1;2;3;4] (* top-level call *)

f [2;3;4] (* first recursive call *)

f [3;4] (* second recursive call *)

f [4] (* third recursive call *)

f [] (* last call *)

If each such recursive call to ^f were to calculate one of the rotations of the original list, what information would ^f be missing? Each call is missing a prefix of the original list!

(*missing prefix*) f [1;2;3;4] []

f [2;3;4] [1]

f [3;4] [1;2]

f [4] [1;2;3]

f [] [1;2;3;4]

If we append the two lists in each row above, we obtain one of the desired permutations of the original list. (One of the permutations,

[1;2;3;4], appears twice—we’ll have to be careful to leave one of them out of the result.)

This suggests that we can solve the rotations problem by creating a helper function that takes an extra parameter—namely, the missing prefix needed to compute one permutation of the original list.

If we were to accumulate these lists together into a list of lists, we would be done. That is, we want a function^fthat works like:

f [1;2;3;4] []=⇒[[1;2;3;4]; [2;3;4;1]; [3;4;1;2]; [4;1;2;3]]

What should ^f do on a tail of the original, assuming we provide the missing prefix?:

f [2;3;4] [1]=⇒[[2;3;4;1]; [3;4;1;2]; [4;1;2;3]]

Do you see the pattern? Each call to the helper function ^f computes some (but not all) of the rotations of the original list. Which ones? The ones beginning with each of the elements of the first input to^f. Observe that at each callf suffix prefix we have thatprefix @ suffixis the original list andsuffix @ prefixis the next rotation to generate.

Function^fshould therefore simply recurse down the suffix list; but at each call it needs to rotate its own head element to the end of the^prefix list, to maintain the relationship described above.

We already know how to put an element at the front of a list—we use

::. How do we put one at the tail? Well, we simply write a second helper function that does the job. We call it ^snoc (because it is the opposite of

cons):

Putting it all together, we can write rotations like so:

(* Add x to the end of the list l *)

let rec snoc (l:int list) (x:int) : int list = begin match l with

| [] -> [x]

| h::tl -> h::(snoc tl x) end

(* Compute some rotations of the list suffix @ prefix, where prefix @ suffix is the "original" list *)

let rec f (suffix:int list) (prefix:int list) : int list list begin match suffix with

| [] -> []

| x::xs -> (suffix@prefix)::(f xs (snoc prefix x)) end

(* The top-level rotations function simply calls f with the empty prefix *)

let rotations (l:int list) = f l []

Infinite loops: Non-structural recursion

All of the examples list processing functions described above are guaran-teed to terminate. Why? Because every list is contains only finitely many elements and each of the recursive calls in a structurally recursive function is invoked on a strictly shorter list (the tail). This means that at some point the chain of recursion will bottom out at the empty list.

OCaml does not strictly enforce that all list functions be structurally recursive. Consider the following example, in which the ^loop function calls itself “recursively” on the entire list, rather than just on the tail:

let loop (l:int list) : int = begin match l with

| [] -> 0

| h::tl -> 1 + (loop l) end

Watch what happens when we run this program on the list^[1]:

loop [1]

7−→ (substitute^[1]for l in the body of loop)

begin match [1] with

| [] -> 0

| h::tl -> 1 + (loop l) end

7−→ (the second case matches)

1 + (loop l) (* uh oh! *)

7−→ . . . 7−→

1 + (1 + (1 + (1 + (loop l))))

7−→ (the program keeps running forever)

If you find one of your programs mysteriously looping, a non-structural recursive call may be the culprit.