[Haskell-cafe] Computing a sorted list of products lazily

[Jason Dagit]

Hello,

A colleague of mine recently asked if I knew of a lazy way to solve
the following problem:
Given two sets of sorted floating point numbers, can we lazily
generate a sorted list of the products from their Cartesian product?

The algorithm should return the same result as:
sortProduct a b = sort [ x * y | x <- a, y <- b ]

But, my friend is not satisfied with the strictness of sort.  In
particular, he doesn't want to have to hold the whole list in memory
to sort it.  He would like to compute the results one product at a
time and in the correct order.

Is there an existing algorithm for this problem?  We searched but we
don't seem to know the right search terms.  Additionally, my friend is
not writing this in Haskell, but a Haskell solution is fine because we
should be able to transform it into a Java solution by hand.

We think we know an algorithm that will produce the right result but
it's a bit messy and we doubt we're the first to tackle this problem.
Any help would be greatly appreciated.  Thanks in advance!

Jason