Leniwy produkt kartezjański w Haskell

Question

Chciałbym wygenerować dość duży, ale skończony, kartezjański produkt w Haskell, który muszę następnie iterować (myślę, że funkcja podziału na model pola średniego). Naturalną rzeczą do zrobienia używa sequence coś takiego:

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

Niestety, dla dużej n, to nie mieści się w pamięci i biegnę z hałdy, jak tylko poprosić o length l na przykład. Potrzebowałabym sposobu, żeby leniwie zrobić to samo. Skończyło się „odkrywając” Base-3 arytmetyki, tak,

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 

(które działa), ale wydaje się, jakby odkrywanie koła na nowo, a poza tym to jest zbyt szczegółowe. Jaki byłby lepszy leniwy sposób generowania produktu?

Answer 1

Im więcej pamięci przyjazny sposób uzyskuje się poprzez wiązanie się w odwrotnej kolejności w stosunku do sekwencji,

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

Jest wolniej ze względu na mniejsze dzielenia się, ale ponieważ pamięć jest twój problem, może to wystarczająco dobre dla ciebie.