I've got two (possibility infinite) lists [a] and [b]. I would like to construct a (possibly infinite) list containing all pairs [(a, b)], each exactly once. This seems like it ought to be right up Haskell's alley, but I'm stuck.
I started with the classic diagonalization of the rationals:
pairs :: [a] -> [b] -> [(a, b)]
pairs x y =
let diag (lhs, rhs) = zip lhs $ reverse rhs
in concatMap diag $ zip (inits x) (inits y)
This works by "enumerating the diagonals:" it takes an initial subsequence of (say) length 4 from both lists, reverses one of them, and zips them together. Repeat for all initial subsequences of all lengths, and concatenating all the results. This works when both lists are infinite.
However this fails if either list is finite. The problem is that we stop once we reach the longest diagonal, so the lower-right triangular half of the grid is not enumerated. e.g. inits [1, 2] results in [[1], [1, 2], [2, 1]], and we never enumerate the value (2, 2).
So I blurted out a function to generate both forwards and backwards diagonals:
inits_bidir :: [a] -> [[a]]
inits_bidir [] = []
inits_bidir x =
let forwards = tail $ inits x -- skip empty
backwards = map reverse $ (tail . reverse . tail . inits . reverse) x
in forwards ++ backwards
pairs :: [a] -> [b] -> [(a, b)]
pairs x y =
let diag (lhs, rhs) = zip lhs $ reverse rhs
in concatMap diag $ zip (inits_bidir x) (inits_bidir y)
example:
> inits_bidir [1..3]
[[1],[1,2],[1,2,3],[2,3],[3]]
Now this works if both lists are the same length (possibly infinite). But it fails if one list is longer than the other, because we're still enumerating the diagonals of a square, but our matrix is rectangular.
Before I dig myself in even deeper, is there a better way to go about this?
