Haskell中的惰性笛卡尔积

Question

我想在Haskell中生成一个相当大但有限的笛卡尔积，然后需要对其进行迭代（请考虑均值场模型的分区函数）。自然的做法是使用sequence，如下所示：

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

[不幸的是，对于大的n，这不适合内存，例如，当我要求length l时，我就用光了堆。我需要一种方法来懒惰地做同样的事情。我最终像这样“重新发现” base-3算术，

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

（有效），但感觉就像是在重新发明轮子，而且它太具体了。什么是生成产品的更好的懒惰方式？

Answer 1

与序列相比，通过以相反的顺序进行绑定可以获得更友好的内存方式，

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

由于共享较少，速度较慢，但​​是由于内存是您的问题，所以也许对您来说足够好了。