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

prefixes, which is like the ^{suffixes} example above, but instead 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 ^{suffixes} was? Suppose we’re
try-ing to calculate^{prefixes} ** ^{[1;2;3]}**. Following the structural recursion pattern, we
would expect to call

^{prefixes}on 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 ** ^{1}**, we need to
compute

^{prefixes}for the entire list

**. Looking for a pattern, it seems that we need to put**

^{[1;2;3]}**at the head of each of the prefixes of**

^{1}**. 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**

^{[2;3]}^{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 trying to
com-pute a function ^{rotations} that, 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 ^{rotations}would work on the result of a
re-cursive call illustrates why there might be a need for a helper function. When we
use^{rotations}on 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 between^{rotations} ** ^{[2;3;4]}**and

^{rotations}

**seems very nontrivial—it seems like we have to intersperse the head**

^{[1;2;3;4]}**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.**

^{1}Here’s another approach that simplifies the solution. Consider what
informa-tion from the original list that we have at each recursive call to some funcinforma-tion^{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
orig-inal 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 func-tion 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^{f}that 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
be-ginning with each of the elements of the first input to ^{f}. Observe that at
each call f suffix prefix we have that ^{prefix} ^{@}^{suffix} is the original list and

suffix **@** prefixis the next rotation to generate.

Function^{f}should 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 guaranteed 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
“recur-sively” 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 recur-sive call may be the culprit.