How can I calculate the cartesian product of n lists of different types?

Question

The following code (sorry, I do not remember where I copied it from) calculates the cartesian (or outer) product of two lists that may be of different types:

let outer2 xs ys = 
    xs |> List.collect (fun x -> ys |> List.map (fun y -> x, y))

From this one can write a function that calculates the outer product of two lists that are the elements of a 2-tuple:

let outerTup tup = outer2 (fst tup) (snd tup)

It is not hard to extend this to the case of a tuple containing three lists. However, I could not find a way to write a function that would take a tuple of any length whose elements are lists (possibly of different types) and calculate the cartesian product of the lists.

Here in SO and also in F# Snippets there are several solutions for the problem where all the lists have the same type (in which case the argument is a list of lists). But I have not seen an example where the lists are of different types.

Any suggestions?

Answer 1

Theoretically you can't do exactly what you want to do, but you can get pretty close to it. The reason why you cannot create such a function is because of static typing.

With tuples you can combine values of different types, but to ensure type-safety a tuple must be fixed-size and the type of every element must be known.

A list can contain a variable amount of elements, but because of this the type of every element must be the same. Otherwise you couldn't work with it in a static typed language.

In a dynamic typed language you could for example create a single function that takes a list of list (A) and another list (B). Then you add every element from B to every list inside of A and you are done. You also could do the same in a static typed language with two ideas:

1. You convert every element of the list to object first.
2. You create a Discriminated Union of every type first.

The first idea would mean you need a lot of down and up-casting, this is usually not what you want in a static-typed language. The second approach works but you must convert every single list to your DU type (you also need to create a DU), and later on you need to pattern match. Technically it is the same as 1. only in a more type-safe way.

Another approach and that is what I recommend is the usage of an Applicative. An applicative actually means you upgrade a function so every argument of a function can be an option, list and so on. So you first create an apply function like this:

let apply fs xs = [
    for f in fs do
    for x in xs do
        yield f x
]
let (<*>) = apply

once you have such a function you can write something like this:

[fun a b c d -> (a,b,c,d)]
    <*> [1..5]
    <*> ["a";"b"]
    <*> [(0,0);(1,1)]
    <*> [100;200]

This then returns a list containing:

[(1, "a", (0, 0), 100); (1, "a", (0, 0), 200); (1, "a", (1, 1), 100);
 (1, "a", (1, 1), 200); (1, "b", (0, 0), 100); (1, "b", (0, 0), 200);
 (1, "b", (1, 1), 100); (1, "b", (1, 1), 200); (2, "a", (0, 0), 100);
 (2, "a", (0, 0), 200); (2, "a", (1, 1), 100); (2, "a", (1, 1), 200);
 (2, "b", (0, 0), 100); (2, "b", (0, 0), 200); (2, "b", (1, 1), 100);
 (2, "b", (1, 1), 200); (3, "a", (0, 0), 100); (3, "a", (0, 0), 200);
 (3, "a", (1, 1), 100); (3, "a", (1, 1), 200); (3, "b", (0, 0), 100);
 (3, "b", (0, 0), 200); (3, "b", (1, 1), 100); (3, "b", (1, 1), 200);
 (4, "a", (0, 0), 100); (4, "a", (0, 0), 200); (4, "a", (1, 1), 100);
 (4, "a", (1, 1), 200); (4, "b", (0, 0), 100); (4, "b", (0, 0), 200);
 (4, "b", (1, 1), 100); (4, "b", (1, 1), 200); (5, "a", (0, 0), 100);
 (5, "a", (0, 0), 200); (5, "a", (1, 1), 100); (5, "a", (1, 1), 200);
 (5, "b", (0, 0), 100); (5, "b", (0, 0), 200); (5, "b", (1, 1), 100);
 (5, "b", (1, 1), 200)]

If you don't want to create the operator <*> you also could write:

[fun a b c d -> (a,b,c,d)]
    |> apply <| [1..5]
    |> apply <| ["a";"b"]
    |> apply <| [(0,0);(1,1)]
    |> apply <| [100;200]

but I usually discourage the usage of <|. I would prefer this instead:

let ap xs fs = [
    for f in fs do
    for x in xs do
        yield f x
]

[fun a b c d -> (a,b,c,d)]
    |> ap [1..5]
    |> ap ["a";"b"]
    |> ap [(0,0);(1,1)]
    |> ap [100;200]

The only thing you must create on-the-fly is the first-line. A function that maps four, five, six, ... arguments to a tuple.

If you want to know more about Applicatives and how it works exactly, I have written two blog-posts about this topic:

http://sidburn.github.io/blog/2016/04/13/applicative-list http://sidburn.github.io/blog/2016/03/31/applicative-functors

Answer 2

According to this StackOverflow question, it may not be possible to write a function that takes in a tuple of any length as argument.

Variable length tuples in f#

That question is asked a long time ago, and I am not sure if F# has any updates and changes that makes it possible.