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.

Nephrotomy

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.

Shod

Your last output list is missing (1,105). It is still quite impressive. I’ve not had a chance to run Norman Ramsey’s but it looks terrific. Cartesian products are fascinating. I generated one with mergeAll in which any non-duplicate was a prime. – Exsanguinate

@Exsanguinate it's the very next one, try take 21 $ kart_i3 [1..] [100..] or kart_i3 [1..] [100..] !! 20 or elemIndex (1,105) $ kart_i3 [1..] [100..]. Haskell's indices used by !! are 0-based. thanks to your question I'll remember about elemIndex from now on, hopefully; thanks! (I now realise that it's what I needed to use here, alas, it was lots of trial and error instead, d'oh) – Shod

@will_ness Diagonal’s can use triangular numbers. We always use multiples of 5 or 10 when taking the first part of an infinite list. If we want 20 then tri n = foldl (+) 1 [2..n] and revtn n = floor (sqrt (n*2)) We revtn 20 and it returns 6 the length of the of the top row. tri 6 returns 21, the number of elements in the diagonal and a triangular number. You make Haskell amazing with your Lambda Calculus Generator, replete with ((^x.(x x)) (^x.(x x))). – Exsanguinate

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)]

Edmanda

null $ filter (\(x,y)-> y >0) $ kart [0..] [0..] gives False but null $ filter (\(x,y)-> x >0) $ kart [0..] [0..] does not terminate; your kart only includes multiple xs if ys is finite. – Slotnick

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]]

Eudemonics