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

Martijn van Steenbergen martijn at van.steenbergen.nl
Fri Apr 17 18:31:50 EDT 2009


Hi Daniel,

I love your solution. Very elegant.

Daniel Fischer wrote:
> sortedProducts xs ys = foldr merge1 [] [map (*x) ys | x <- xs]
> 
> merge1 (x:xs) ys = x:merge xs ys
> merge1 [] ys = ys
> 
> merge xs@(x:xt) ys@(y:yt)
>     | x < y    = x:merge xt ys
>     | otherwise = y:merge xs yt
> (or remove duplicates, if you wish)

Small addition: if you want this to run on finite input as well, add 
this case:

 > merge xs ys = xs ++ ys

Martijn.



More information about the Haskell-Cafe mailing list