如何计算 n 个不同类型列表的笛卡尔积？

Question

下面的代码（对不起，我不记得我从哪里复制的）计算两个可能不同类型的列表的笛卡尔（或外）积：

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

由此可以编写一个函数来计算作为二元组元素的两个列表的外积：

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

不难将其扩展到包含三个列表的元组的情况。但是，我找不到一种方法来编写一个函数，该函数接受一个任意长度的元组，其元素是列表（可能是不同类型）并计算列表的笛卡尔积。

在 SO 和 F# Snippets 中，对于所有列表都具有相同类型（在这种情况下，参数是列表列表）的问题，有多种解决方案。但是我还没有看到列表是不同类型的例子。

有什么建议吗？

Answer 1

这不是 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 2

根据这个 Whosebug 问题，可能无法编写一个将任意长度的元组作为参数的函数。

Variable length tuples in f#

很久以前就有人问过这个问题，我不确定 F# 是否有任何更新和更改使其成为可能。

Answer 3

理论上你不能完全按照你想做的去做，但你可以非常接近它。你不能创建这样一个函数的原因是静态类型。

使用元组，您可以组合不同类型的值，但为了确保类型安全，元组必须是固定大小的，并且必须知道每个元素的类型。

列表可以包含可变数量的元素，但因此每个元素的类型必须相同。否则您无法使用静态类型语言使用它。

例如，在动态类型语言中，您可以创建一个函数，该函数接受一个列表 (A) 和另一个列表 (B)。然后将 B 中的每个元素添加到 A 中的每个列表中，就完成了。您也可以使用两种想法在静态类型语言中执行相同的操作：

首先将列表中的每个元素转换为 object。
您首先创建一个所有类型的可区分联盟。

第一个想法意味着你需要大量的向下和向上转型，这通常不是你想要的静态类型语言。第二种方法可行，但您必须将每个列表转换为您的 DU 类型（您还需要创建一个 DU），稍后您需要进行模式匹配。从技术上讲，它与 1. 相同，只是类型更安全。

我推荐的另一种方法是使用 Applicative。一个应用程序实际上意味着你 upgrade 一个函数所以函数的每个参数都可以是一个 option, 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]

然后 returns 一个列表包含：

[(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.github.io/blog/2016/04/13/applicative-list http://sidburn.github.io/blog/2016/03/31/applicative-functors

如何计算 n 个不同类型列表的笛卡尔积？

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

f#

list

cartesian-product