不幸的是,对于大的 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中的懒惰笛卡尔积
发布评论