How can I calculate the cartesian product of n lists of different types?
cartesian-product, f#, list
Solution
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:
- You convert every element of the list to `object` first.
- 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
Problem
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?