Haskell中的"Lazy cartesian product"

Question

我希望在Haskell中生成一个相当大但有限的笛卡尔积，然后需要对其进行迭代（类似于平均场模型的分区函数）。使用sequence是一个自然的选择，像这样：

l = sequence $ replicate n [0,1,2]

不幸的是，对于大的n，这并不适合内存，并且当我要求例如长度l时，我很快就会用尽堆栈。我需要一种懒加载实现相同功能的方法。最终我重学了三进制算术，像这样：

nextConfig []     = []
nextConfig (0:xs) = 1:xs
nextConfig (1:xs) = 2:xs
nextConfig (2:xs) = 0:(nextConfig xs)

ll = take (3^n) $ iterate nextConfig $ replicate n 0

(这个方法)虽然可行，但感觉有点重复造轮子，而且它太具体化了。有没有更好的方式来懒惰地生成产品呢？

- Vincent Beffara

---

你关心结果中元素的顺序吗？ - augustss

不，只要没有重复就可以。 - Vincent Beffara

你需要 n 多大？ - dave4420

大概是20或30吧，我现在并不关心计算时间，但肯定3^n已经超出了RAM的大小。 - Vincent Beffara

Answer 1

更加节省内存的方式是与序列相比按相反的顺序进行绑定。

foo 0 _ = [[]]
foo k xs = [h:t | t <- foo (k-1) xs, h <- xs]

由于共享较少，因此速度会较慢，但由于内存是您的问题，所以也许这已经足够了。

- Daniel Fischer

---

酷！我得更深入地调查一下它为什么起作用，但它确实有效。我修改了它为 foo (l: ls) = [h: t | t <- foo2 ls, h <- l]（谁知道我是否总是需要一个立方体），它也起作用了。谢谢！ - Vincent Beffara

为什么列表推导比用于列表的do-notation（在“sequence”中使用）更有效？我可以从Haskell2010报告中看到它们都被展开为“concatMap”？ - haskelline

@brence：请查看Duncan Coutts在Reddit上对这个问题的回答：为什么列表推导式中的守卫比do-notation中的快？ - danr

从那里看来，列表推导式似乎被解糖成了foldr。奇怪的是，一个天真的foldr方法对于笛卡尔积（至少我尝试过的那个）会像sequence一样破坏惰性... - Vincent Beffara

@danr，几年前我更改了concatMap的定义和/或[]的Monad实例，因此现在它应该与列表推导版本基本相同。据我回忆，我们现在定义concatMap f xs = [f x | x <- xs]或类似的内容。 - dfeuer

Answer 2

无限列表的模式是从左上角a1开始，然后依次为a2到b1、a3到c1

a1 a2 a3 a4
b1 b2 b3 b4
c1 c2 c3 c4
d1 d2 d3 d4

即a1，a2 b1，a3 b2 c1，a4 b3 c2 d1 逗号分隔的字母为 a ab abc abcd和数字 1 21 321 4321

无限列表输出应首先以a1对角线增长，然后添加2个对角线，然后添加3个对角线，依此类推。

上述任何一个单个字母或数字都必须向反方向发展。

diag xs ys = [(a,b)| (m,n) <- zip (inits xs) (inits ys), (a,b) <- zip m $ reverse n ]

对于每个 (m,n) 对，我更喜欢一次性反转所有元素，而不是重复单个操作。我认为只有通过连续反转列表才能实现无限列表的反转。

rsl = tail.scanl (flip (:)) []

take 5 $ rsl [1..]

[[1],[2,1],[3,2,1],[4,3,2,1],[5,4,3,2,1]]

然后逐个处理每个列表。 zip 在每次迭代中限制非反转列表。

plr xs ys = [ (a,b) | ls <- rsl xs, (a,b) <- zip ls ys ]

sort.take 10.plr ['a'..] $ [1..]

[('a',1),('a',2),('a',3),('a',4),('b',1),('b',2),('b',3),('c',1),('c',2),('d',1)]

sort，因为按对角线取值意味着它们不像上面的第一个线性列表那样有序。 sort 是从 Data.List 导入的。

顺便说一下，因为这是沿着对角线遍历，所以三角形数也会出现。我在上面使用了 take 10，三角形数是：

take 11 [sum ls | ls <- rsl [1..]]

[1,3,6,10,15,21,28,36,45,55,66]

- fp_mora

---

嗨，这个非常古老的问题上有一些活动！但我不确定你的回复与它有何关系，也许你是打算回答另一个问题？ - Vincent Beffara

“diag”是一种惰性笛卡尔积。试试看。正如我所说，我更喜欢使用惰性函数来实现反转列表，即惰性“rsl”。 “plr”是另一个使用惰性“rsl”的惰性笛卡尔积函数。如果您不在所有这些函数中使用“take”，它们将永远运行。 - fp_mora