Lazy cartesian product in Haskell
cartesian-product, haskell, lazy-evaluation
Solution
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.
Problem
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?