Haskell中的懒惰笛卡尔积 [英] Lazy cartesian product in Haskell

问题描述

我想在Haskell中生成一个相当大但有限的Cartesian产品，然后我需要迭代（考虑平均场模型的分区函数）。自然而然的做法是使用 sequence ，如下所示：

  l =序列$ replicate n [0,1,2] 
  

不幸的是，对于大的 n ，这不适合在内存中，并且只要我要求 length l 就会用完堆。我需要一种方式来懒惰地做同样的事情。

  nextConfig [] = [] 
 nextConfig（ （1：xs）= 2：xs 
 nextConfig（2：xs）= 0：（nextConfig xs）
 
 ll = take （3 ^ n）$ iterate nextConfig $ replicate n 0 
  

（这有效）但它感觉像重新创建这个轮子，除此之外还有很多具体的东西。什么会是更好的懒惰的方式来产生产品？

解决方案

与序列相比，

  foo 0 _ = [[]] 
 foo k xs = [h：t | t < -  foo（k-1）xs，h < -  xs] 
  

由于分享较少，但因为记忆是你的问题，所以对你来说也许已经足够了。

I would like to generate a rather large but finite Cartesian product in Haskell, which I need to then iterate on (think partition function of a mean-field model). The natural thing to do uses sequence, like this:

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

Unfortunately, for large n, this does not fit in memory and I run out of heap as soon as I ask for length l for instance. I would need a way to do the same thing lazily. I ended up "rediscovering" base-3 arithmetics, like this,

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

(which works) but it feels like reinventing the wheel, and besides it is much too specific. What would be a better lazy way to generate the product?

解决方案

The more memory-friendly way is obtained by binding in reverse order compared to sequence,

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

It is slower due to less sharing, but since memory is your problem, maybe it's good enough for you.

这篇关于Haskell中的懒惰笛卡尔积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！