在Haskell中，笛卡尔积“生成器”（不是列表）是什么？

Question

我对函数式编程并不熟悉，现在我想解决一个问题：递归生成一组列表的笛卡尔积。

我需要的功能与 sequence 完全相同（如此处所述：Calculate n-ary Cartesian Product），只是我不想将整个内容表示为列表。目前我正在使用 sequence，但遇到了类似于这里描述的问题变体：Summing a large list of numbers is too slow。

例如，sequence [[1,2,3],[1,2,3]] 会产生 [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]。每个组合（例如 [1,2]）都可以接受作为一个列表进行处理，我只是想避免构建长列表，而是在计算时递归处理数据。我该如何处理？

目前我正在做类似于以下 ghci 示例的操作：

> let stuff = sequence $ replicate 10 [0..9]
> let morestuff = map (sum . take 2 . reverse . sort) stuff
> sum morestuff

最后一个命令太慢了，非常非常慢。

- Harris M Snyder

---

“processing the data recursively as it is calculated” 的确切含义是什么？这正是 Haskell 中惰性求值的工作方式。 - Bergi

最后一个命令将强制计算每个组合（总共有10^10个）- 我认为你首先应该专注于你的算法，而不是评估细节。 - Random Dev

对于每个组合，您只使用两个最大的数字并将它们相加 - 因此您根本不需要笛卡尔积（您只需再次对其进行排序）...只需寻找以已排序的方式生成它们的方法（并在之后乘以排列数的数量）...我认为这实际上更像是一个数学问题（这是项目欧拉吗？），我不想透露太多，因为它可能是某个比赛的一部分^^ - Random Dev

尝试在每个“let”之间强制使用列表，你会发现所有阶段都花费了大量时间——惰性只意味着除非你提前强制，否则只能在最后看到它。在repl中强制事物的一种方法是使用Control.DeepSeq中的rnf。话虽如此，您正在生成和求和大约10^10个东西，也就是说十亿。因此，无论您如何编写代码，我都不认为这样做会很顺利。 - sclv

@Bergi，我的意思不是建立所有组合的列表。 - Harris M Snyder

Answer 1

将我的评论转化为答案：

最后一行出现特别慢的唯一原因是它强制执行了所有其他行的工作，而这些工作通常是惰性累积的。因此，每个子列表都是按需处理的（尽管每个子列表上的排序会强制执行整个子列表）。

要观察到所有阶段都需要时间，而不仅仅是最后一个阶段，我们可以在进行过程中使用Control.DeepSeq中的rnf来强制中间结果。

但生成和求和大约十亿个元素需要一些时间。正如其他人所观察到的那样，这是一个你应该更多地考虑如何以更聪明的方式获得所需结果的情况（即可以删除或转换哪些中间步骤而不改变结果，以及可以利用哪些对称性）而不仅仅是更有效地执行暴力方法的情况。

- sclv