Cartesian product of infinite lists in Haskell

Question

I have a function for finite lists

> kart :: [a] -> [b] -> [(a,b)]
> kart xs ys = [(x,y) | x <- xs, y <- ys]

but how to implement it for infinite lists? I have heard something about Cantor and set theory.

I also found a function like

> genFromPair (e1, e2) = [x*e1 + y*e2 | x <- [0..], y <- [0..]]

But I'm not sure if it helps, because Hugs only gives out pairs without ever stopping.

Thanks for help.

Answer 1

Your first definition, kart xs ys = [(x,y) | x <- xs, y <- ys], is equivalent to

kart xs ys  =  xs >>= (\x ->
               ys >>= (\y -> [(x,y)]))

where

(x:xs) >>= g  =  g x ++ (xs >>= g)
(x:xs) ++ ys  =  x : (xs ++ ys)

are sequential operations. Redefine them as alternating operations,

(x:xs) >>/ g  =  g x +/ (xs >>/ g)
(x:xs) +/ ys  =  x : (ys +/ xs)
[]     +/ ys  =  ys

and your definition should be good to go for infinite lists as well:

kart_i xs ys  =  xs >>/ (\x ->
                 ys >>/ (\y -> [(x,y)]))

testing,

Prelude> take 20 $ kart_i [1..] [101..]
[(1,101),(2,101),(1,102),(3,101),(1,103),(2,102),(1,104),(4,101),(1,105),(2,103)
,(1,106),(3,102),(1,107),(2,104),(1,108),(5,101),(1,109),(2,105),(1,110),(3,103)]

courtesy of "The Reasoned Schemer". (see also conda, condi, conde, condu).

---

another way, more explicit, is to create separate sub-streams and combine them:

kart_i2 xs ys = foldr g [] [map (x,) ys | x <- xs]
  where
     g a b = head a : head b : g (tail a) (tail b)

this actually produces exactly the same results. But now we have more control over how we combine the sub-streams. We can be more diagonal:

kart_i3 xs ys = g [] [map (x,) ys | x <- xs]
  where                                       -- works both for finite
  g [] [] = []                                --  and infinite lists
  g a  b  = concatMap (take 1) a
            ++ g (filter (not . null) (take 1 b ++ map (drop 1) a))
                 (drop 1 b)

so that now we get

Prelude> take 20 $ kart_i3 [1..] [101..]
[(1,101),(2,101),(1,102),(3,101),(2,102),(1,103),(4,101),(3,102),(2,103),(1,104)
,(5,101),(4,102),(3,103),(2,104),(1,105),(6,101),(5,102),(4,103),(3,104),(2,105)]

With some searching on SO I've also found an answer by Norman Ramsey with seemingly yet another way to generate the sequence, splitting these sub-streams into four areas - top-left tip, top row, left column, and recursively the rest. His merge there is the same as our +/ here.

---

Your second definition,

genFromPair (e1, e2) = [x*e1 + y*e2 | x <- [0..], y <- [0..]]

is equivalent to just

genFromPair (e1, e2) = [0*e1 + y*e2 | y <- [0..]]

Because the list [0..] is infinite there's no chance for any other value of x to come into play. This is the problem that the above definitions all try to avoid.

Answer 2

Prelude> let kart = (\xs ys -> [(x,y) | ls <- map (\x -> map (\y -> (x,y))  ys)  xs, (x,y) <- ls])
Prelude> :t kart
kart :: [t] -> [t1] -> [(t, t1)]
Prelude> take 10 $ kart [0..] [1..]
[(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9),(0,10)]
Prelude> take 10 $ kart [0..] [5..10]
[(0,5),(0,6),(0,7),(0,8),(0,9),(0,10),(1,5),(1,6),(1,7),(1,8)]

Answer 3

you can think of the sequel as

0:          (0, 0)
           /      \
1:      (1,0)    (0,1)
       /     \  /     \
2:  (2,0)   (1, 1)   (0,2)
...

Each level can be expressed by level n: [(n,0), (n-1, 1), (n-2, 2), ..., (0, n)]

Doing this to n <- [0..]

We have

cartesianProducts = [(n-m, m) | n<-[0..], m<-[0..n]]