Am Freitag 17 April 2009 23:41:18 schrieb 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?
If the numbers are nonnegative, you could use sortedProducts xs ys = foldr merge1 [] [map (*x) ys | x <- xs] merge1 (x:xs) ys = x:merge xs ys merge1 [] ys = ys merge xs@(x:xt) ys@(y:yt) | x < y = x:merge xt ys | otherwise = y:merge xs yt (or remove duplicates, if you wish) Since the lists are sorted and the numbers nonnegative, each (map (*x) ys) is sorted and the heads of these are sorted, too, therefore we can use merge1, which makes the fold lazy enough to work even on infinite lists (it is not very fast, though, if speed is crucial, you might be better off to sort in chunks).
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