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

[Daniel Fischer]

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