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