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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to