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

[Tillmann Rendel]

Jason Dagit wrote:
> 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 ]

First create a matrix of all the products, represented as a list of 
non-empty lists such that the inner lists are sorted, and the outer list 
is sorted by the first elements of the inner lists. Then repeatedly 
remove the first element of the first list, and reorder the list-of-lists.

 > module SortProduct where
 >
 > import Data.List (insertBy)
 > import Data.Function (on)
 >
 > products a b = [[x * y | x <- a] | y <- b]
 >
 > toList [] = []
 > toList ([x] : rest) = x : toList rest
 > toList ((x : xs) : rest)
 >   = x : toList (insertBy (compare `on` head) xs rest)
 >
 > sortProduct a b = toList (products a b)

     Tillmann