How can I write this function only by using recursion in F#?

Question

let rec n_cartesian_product = function
    | [] -> [[]]
    | x :: xs ->
      let rest = n_cartesian_product xs 
      List.concat (List.map (fun i -> List.map (fun rs -> i :: rs) rest) x)

Hello! I wrote this function but I need to write it without using any List.* built-in functions. Since there's an inner function that calls an outer function, I assume I must define two mutually recursive functions.

Defining a concat function seemed easy:

let rec list_concat ( lst : 'a list list ) : 'a list =
match lst with 
[]    -> []
|x::xs  -> x @ (list_concat xs)

The problem is, I'm stuck at the definition of the functions which yield the argument for concat:

let rec fun_i rest =
    match rest with
    [] -> []
    |x::xs -> fun_rs

and fun_rs =
fun_i :: fun_rs

I can't seem to devise a proper solution. Can you help me?

edit: for instance, given this input

[["A";"a"];["B";"b"];["C";"c"]]

I want this output:

[["A"; "B"; "C"]; ["A"; "B"; "c"]; ["A"; "b"; "C"]; ["A"; "b"; "c"];
 ["a"; "B"; "C"]; ["a"; "B"; "c"]; ["a"; "b"; "C"]; ["a"; "b"; "c"]]

Answer 1

N-Cartesian Product

To define the n cartesian product recursively, the easiest method is just to make recursive definitions of the functions used in your original (non-recursive) example:

let rec list_concat lst =
    match lst with 
    |[]    -> []
    |x::xs  -> x @ (list_concat xs)

let rec list_map f lst =
    match lst with
    |[] -> []
    |x::xs -> (f x) :: list_map f xs

let rec n_cartesian_product = 
    function
    | [] -> [[]]
    | x :: xs ->
      let rest = n_cartesian_product xs 
      list_concat (list_map (fun head -> list_map (fun tail -> head :: tail) rest) x)

In terms of writing idiomatically in F#, it's best to write using more general functions (like fold), rather than making a lot of custom functions with explicit recursion. So, you could define some additional functions:

let list_collect f = list_concat << list_map f

let rec list_fold f acc lst =
    match lst with
    |[] -> acc
    |hd::tl -> list_fold f (f acc hd) tl

let n_cartesian_product_folder rest first = 
    list_collect (fun head -> list_map (fun tail -> head :: tail) rest) first

Then we can redefine n_cartesian_product simply as:

let n_cartesian_product2 lst = list_fold (n_cartesian_product_folder) [[]] lst

If we were using F# core library functions (rather than custom recursive implementations) this approach would involve more standard code with less to go wrong.

Cartesian Product (I'll leave this part here since apparently it was useful)

Define a function that takes a list of 'a and make a list of 'b * 'a where all of the things of type 'b are some supplied element y.

/// take a list of 'a and make a list of (y, 'a)
let rec tuplify y lst =
    match lst with
    |[] -> []
    |x::xs -> (y, x) :: (tuplify y xs)

Then define a function that recurses through both my lists, calling tuplify on the current element of the first list and the entire second list and concat that with the recursive call to cartesian product.

/// cartesian product of two lists
let rec cartesianProduct lst1 lst2 =
    match lst1 with
    |[] -> []
    |x::xs -> tuplify x lst2 @ (cartesianProduct xs lst2)