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

Question

The following code (sorry, I don’t remember where I copied it) calculates the Cartesian (or external) product of two lists, which can be of different types:

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

From this we can write a function that calculates the external product of two lists, which are elements of a 2-tuple:

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

It is easy 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 computes the Cartesian product of lists.

Here in SO, as well as in F # Snippets, there are several solutions to the problem where all lists are of the same type (in this case, the argument is a list of lists). But I have not seen an example where lists have different types.

Any suggestions?

Answer 1

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

You can combine values ​​of different types with tuples, but to ensure type safety, the tuple must be fixed, and the type of each element must be known.

, - . .

, , , (A) (B). B A, . :

• object.
• .

, , , . , DU ( DU), . , 1. .

, , , . , , , list .. , apply :

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

, - :

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

, :

[(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)]

<*>, :

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

<|. :

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]

, " " - . , , , ,... .

Applicatives , :

http://sidburn.imtqy.com/blog/2016/04/13/applicative-list http://sidburn.imtqy.com/blog/2016/03/31/applicative-functors

Answer 2

n. FSharp .

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

let outerTup2 (a,b) = outer2 a b

let outerTup3 (a,b,c) = 
  a
  |> outer2 b
  |> outer2 c
  |> List.map (fun (c,(b,a))->a,b,c)

let outerTup4 (a,b,c,d) =
  a
  |> outer2 b
  |> outer2 c
  |> outer2 d
  |> List.map (fun (d,(c,(b,a)))->a,b,c,d) 

// etc...

outerTup2 ([1;2],[3;4])

outerTup3 ([1;2],[3;4],[5;6])

outerTup4 ([1;2],[3;4],[5;6],[7;8])

Answer 3

StackOverflow, , , .

f #

, , F # , .