Haskell- Two lists into a list of tuples

Question

I am trying to implement a function (described below) that takes two lists (each or both may be infinite) and return a list of tuples of all the possible pairs of elements between the lists

zipInf :: [a] -> [b] -> [(a,b)]

(e.g the output should be like this, but doesn't have to be exactly like this)

zipInf [0 .. 2] ['A' .. 'C'] ~> [(0,'A'),(1,'A'),(0,'B'),(1,'B'),(0,'C'),(2,'A'),(2,'B'),(1,'C'),(2,'C')]

zipInf [] [0 ..] ~> []

zipInf [0 ..] [] ~> []

take 9 (zipInf ['A'] [0 .. ]) ~> [('A',0),('A',1),('A',2),('A',3),('A',4),('A',5),('A',6),('A',7),('A',8)]

I've started implementing it like this:

zipInf :: [a] -> [b] -> [(a,b)]
zipInf [] _ = []
zipInf _ [] = []
zipInf

I wanted to feed the list into a helper function to produce the lists but the one I made fails to compile and don't know how to handle infinite lists

Helper function-

oneList :: [a] -> [b] [(a,b)]
oneList [] _ = []
oneList x:xs y:ys = [(x,y)] ++ oneList

Answer 1

This is a great exercise!

If we lay out the pairs of your input in an infinite table:

(0,A)  (1,A)  (2,A)  (3,A) ...
(0,B)  (1,B)  (2,B)  (3,B) ...
(0,C)  (1,C)  (2,C)  (3,C) ...
(0,D)  (1,D)  (2,D)  (3,D) ...
...

The trick is to traverse the table in upward diagonal stripes. Trace the table with your eyes. The stripes of this table are:

(0,A)
(0,B) (1,A)
(0,C) (1,B) (2,A)
(0,D) (1,C) (2,B) (3,A)
...

All the stripes are finite, yet every element of the table is in one of them, so if you concatenate them together every element will appear at a finite position in the concatenated result.

Here's the gameplan I'd suggest:

Implement stripes :: [[a]] -> [[a]] which extracts the list of stripes from an infinite array like above (start by assuming that all lists are infinite, i.e. don't worry about the [] cases; once you have that working, correct it to work on lists that might be finite).

Using stripes, implement diagonal :: [[a]] -> [a] which concatenates all the stripes (this is a one-liner).

Finally, implement your function by applying diagonal of a particular 2D table [[(a,b)]], which is the table I started this answer with (and can be constructed using a nested list comprehension, among other various ways).

Notes:

• The name zip is misleading. This is more like a cartesian product.

• You know you can match patterns inside patterns, right? I.e. if f :: [[a]] -> something

  f ((x:xs):xss) = ...
  

  Gives you x as the first element of the first row, xs is the rest of the first row, and xss is the rest of the table.