Producto cartesiano perezoso en Haskell

Question

Me gustaría generar un producto cartesiano bastante grande pero finito en Haskell, que necesito repetir (piense en la función de partición de un modelo de campo medio). Lo natural que hacer sequence utiliza, como esto:

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

Desafortunadamente, para gran n, esto no encaja en la memoria y se me termina el montón tan pronto como le pido length l por ejemplo. Necesitaría una manera de hacer lo mismo perezosamente. Terminé "redescubrimiento" base-3 aritmética, de esta manera,

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 

(que funciona) pero se siente como reinventar la rueda, y además es demasiado específica. ¿Cuál sería una mejor manera de generar el producto?

Answer 1

La forma más memoria ambiente se obtiene mediante la unión en el orden inverso en comparación con la secuencia,

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

Es más lento debido a la menor compartir, pero puesto que la memoria es su problema, tal vez es lo suficientemente bueno para usted.