[Haskell-cafe] Computing a sorted list of products lazily
Tillmann Rendel
rendel at cs.au.dk
Fri Apr 17 18:45:31 EDT 2009
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
More information about the Haskell-Cafe
mailing list