Haskell中如何构建预排序的无限优先级堆？

我拥有多个数据容器：

[1,2,3]
fromList [4, 42, 77]
Array Vertex [99, 44, 33]
-- The specific containers are just examples. It would be nice to not assume
-- they are Ord instances, already sorted, etc. but that's more of an 
-- ideal to strive for an a hard and fast rule.

期望最终得到一个优先级堆，类似列表推导式的写法生成所有组合：

[(a, b, c) | a <- list1, b <- thing2, ...]

但实际数据量将超过10^12条，显式排序所有元组不可行，希望无需为每个元组分配分数再排序，直接得到预排序的结果。

直接说结论：可行，但得满足特定前提，而且不能用常规的列表推导式直接实现。

必须先明确的前提 #

首先得给每个容器里的元素（或者最终生成的元组）定好优先级规则——毕竟堆是靠比较优先级来排序的，没规则根本没法谈“预排序输出”。另外，如果你的容器本身没排序，第一步得先给每个容器单独排序，这一步的成本和1e12的总组合数比起来完全可以忽略。

具体实现思路 #

1. 单容器预排序：把每个输入容器按你定好的优先级规则单独排好序，比如升序或者降序。
2. 多路归并堆生成有序结果：
   • 初始化一个最小堆（或者最大堆，取决于你需要的优先级方向），把每个容器的第一个元素组成的元组放入堆中。
   • 每次从堆顶取出优先级最高的元组，这就是你要的下一个有序结果；接着检查该元组中每个元素对应的容器是否还有下一个元素，如果有，就替换对应位置的元素为容器的下一个元素，生成新的元组并放回堆中。
   • 重复上述步骤，直到堆为空。

为什么这能避开生成所有元组 #

这种方式每次只生成当前优先级最高的元组，完全不需要提前创建1e12个组合。堆的大小最多等于输入容器的数量（比如3个容器的话，堆里最多同时存在3个元素），内存占用极低。时间复杂度为O(k log m)：其中k是你实际需要输出的元组数量（如果只需要前N个结果，效率会非常高），m是输入容器的个数。

注意事项 #

• 如果必须输出全部1e12个元组，总耗时肯定还是很长，但至少不会因为内存不足崩溃——因为不需要一次性存储所有元组。
• 单个容器的排序规则必须和最终元组的优先级规则兼容。比如如果元组的优先级是先比较第一个元素，再比较第二个，那么每个容器单独排序时也要遵循对应的子规则。

内容的提问来源于stack exchange，提问作者James Strieter