# [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
```