Haskell中的懒惰笛卡尔积

Question

我想在Haskell中生成一个相当大但有限的笛卡尔积,然后我需要迭代(想想平均场模型的分区函数).自然要做的事情sequence,像这样:

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

不幸的是,对于大型n,这不适合内存,一旦我要求,我就会用完堆length l.我需要一种方法来懒散地做同样的事情.我最终"重新发现"基础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]

它由于共享较少而速度较慢,但​​由于记忆是你的问题,也许这对你来说已经足够了.