Get a cartesian-like product of a list of lists, with unequal lengths and a function ('a -> 'b list) is applied to each item

Question

I've been struggling with this for a while now. While I had some long imperative method that worked, I decided to redesign this part:

• Take a list of lists

• Make a list of the first item of each sublist, then again the first item, but from the last sublist the second item, then the third, until that last list is exhausted, do the same for the N-1 sublist, which basically gives a kind of product of all these lists

  In other words: [abc][FG][98] should be evaluated like (apply function f to each item, comma's are for readability): [aF9,aF8,aG9,aG8,bF9,bF8,bG9,bG8,cF9,cF8,cG9,cG8]

• Flatten that and apply a function to each item of the result, which itself returns a list

• These lists are then flattened to return a singly linked list
• When a sublist is empty (call this E), then only sublists 0 .. E-1 are evaluated (not in my example)

Here's a working example which clearly shows its recursive nature, but obviously only goes as deep as three lists:

let rec nestedApply f inp =
    match inp with
    | [] -> []
    | [x] -> x |> List.collect f
    | [x;y] -> 
        x
        |> List.collect (fun a -> y |> List.collect (fun b -> [a;b]))
        |> List.collect f
    | [x;y;z] -> 
        x
        |> List.collect (fun a -> y |> List.collect (fun b -> z |> List.collect (fun c -> [a;b;c])))
        |> List.collect f
    | head::tail ->
        // ??? I gave the following several attempts but couldn't get it right
        nestedApply f tail
        |> List.collect (fun a -> a::head)
        |> List.collect f

I'd prefer a solution that doesn't blow up the stack. Eventually I'll need this to lazy-eval, so I probably resort to sequences, but with lists I think the algorithm will be easiest to think about.

Example: nestedApply (fun a -> [a]) [[1 .. 5];[6;7];[11;12]]

Example output:

[1; 6; 11; 1; 6; 12; 1; 7; 11; 1; 7; 12; 2; 6; 11; 2; 6; 12; 2; 7; 11; 2; 7;
 12; 3; 6; 11; 3; 6; 12; 3; 7; 11; 3; 7; 12; 4; 6; 11; 4; 6; 12; 4; 7; 11; 4;
 7; 12; 5; 6; 11; 5; 6; 12; 5; 7; 11; 5; 7; 12]

As an aside, since this seems like a pretty "normal" algorithm, though it isn't a cartesian product, what is a typical well-known algorithm that this relates closest to?

Answer 1

_{(OP's note: this high level answer led to my implementation in the other answer, thanks Vivek!)}

• The data set you have is called as N-ary tree.

• Here, every node/list element may have number of children between 0 <= children <= N.

Algorithm steps:

• Run through the first list of lists.
• Apply depth first search to every element in the list.
• Make child elements return themselves as a list.
• Make a new empty lists at parent level and add parent element to each returned child list and add it to lists.
• Return the lists.

Pseudocode:

function possibleLists(curr_list){
  my_new_lists = [];
  for each element in curr_list:
     child_lists = possibleLists(element)
     for each child_list in child_lists:
         child_list.add(element)
         my_new_lists.add(child_list)    
     if child_lists.size() == 0: // needed if there were no further deep levels than the level of curr_list elements
         my_new_lists.add(new List().add(child_list)) // you can return current instance to have this kind of chaining.      

  return my_new_lists;
}

Note: If you want to achieve tail-recursion, then you will have to pass path of elements visited to the next recursive call in parameters as a list to be appended in it's child elements.

P.S- I am not a F# coder, so can help you with pseudo code at the maximum.

Answer 2

Thanks to @vivek_23 for providing pointers on the N-ary trees, I read some posts on tree traversal and the like, which wasn't entirely what this was about (please correct me if I'm wrong), but it lead me to a simple, and I believe elegant, solution:

let rec nestedApply f acc inp =
    match inp with
    | [] -> f acc
    | head::tail -> 
        [
            for x in head do
                yield! nestedApply f (x::acc) tail
        ]

In this case, the apply-function f acts on the small sub-lists which have the same length each iteration, but for my particular case it didn't matter (also, it sped things up if the apply-function didn't need to care about the orders of the subsets). To get exactly the behavior as in the original question, use it like this:

> nestedApply List.rev [] [[1 .. 5];[6;7];[11;12]];;
val it : int list =
  [1; 6; 11; 1; 6; 12; 1; 7; 11; 1; 7; 12; 2; 6; 11; 2; 6; 12; 2; 7; 11; 2; 7;
   12; 3; 6; 11; 3; 6; 12; 3; 7; 11; 3; 7; 12; 4; 6; 11; 4; 6; 12; 4; 7; 11; 4;
   7; 12; 5; 6; 11; 5; 6; 12; 5; 7; 11; 5; 7; 12]

A slightly neater solution hides the accumulator:

let nestedApply f inp =
    let rec innerLoop acc inp =
        match inp with
        | [] -> f acc
        | head::tail -> 
            [
                for x in head do
                    yield! innerLoop (x::acc) tail
            ]

    innerLoop [] inp