Interleave of two lists via recursive function (Ocaml)

Question

I am in front of quite a challenge here, and hope that you can provide a little help.

I have tried and searched a lot, but without success.

Here is the problem:

Two lists

List1 : [a1; a2; ...; an]
List2 : [b1; b2; ...; bn]

What is the function that returns a list of ALL the interleaves possible of the two lists RESPECTING the order within each list.

For example :

myFunction [1; 2] ['a'; 'b'; 'c'] = [ 
    [1; 2; 'a'; 'b'; 'c']; 
    [1; 'a'; 2; 'b'; 'c']; 
    [1; 'a'; 'b'; 2; 'c']; 
    [1; 'a'; 'b'; 'c'; 2]; 
    ['a'; 1; 2; 'b'; 'c']; 
    ['a'; 1; 'b'; 2; 'c']; 
    ['a'; 1; 'b'; 'c'; 2]; 
    ['a'; 'b'; 1; 2; 'c']; 
    ['a'; 'b'; 1; 'c'; 2]; 
    ['a'; 'b'; 'c'; 1; 2] 
]

For those who have noticed, it is basically thinking about 2 concurrent programs, and ALL the executions possible when the 2 programs are launched (1 is always before 2, a is always before b and before c, otherwise, all interleaves are possible)

I hope that I was clear, and that you can help me.

Thank you a lot.

Answer 1

Since it is homework, here are a few hints:

1). The function would take two lists of same type 'a list and return an 'a list list.

val interleave: 'a list -> 'a list -> 'a list list

2). If one list is empty, the result is a singleton list consisting of the other one.
3). Let's say you would like to execute interleave on two non-empty lists x::xs and y::ys. There are two kinds of interleaving. The first kind has x as the head of resulting lists, you would put x into the beginning of any list returning from interleave xs (y::ys). The second kind has y as the new head, you would prepend y into any list obtaining from interleave (x::xs) ys.

With these hints, I think you are able to create a recursive function with a few pattern matching cases to solve the problem.