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

[Bulat Ziganshin]

Hello Jason,

Saturday, April 18, 2009, 1:41:18 AM, you wrote:

> The algorithm should return the same result as:
> sortProduct a b = sort [ x * y | x <- a, y <- b ]

i think it's well-known problem. you should write a function merging
infinite list of sorted lists. in assumption that lists are ordered by
their first element this should be doable

-- Function that merge finite lists (kidnapped from Data.List):
merge_lists :: (a -> a -> Ordering) -> [[a]] -> [a]
merge_lists cmp [] = []
merge_lists cmp [xs] = xs
merge_lists cmp xss = merge_lists cmp (merge_pairs cmp xss)

merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
merge_pairs cmp [] = []
merge_pairs cmp [xs] = [xs]
merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss

merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
merge cmp xs [] = xs
merge cmp [] ys = ys
merge cmp (x:xs) (y:ys)
 = case x `cmp` y of
        GT -> y : merge cmp (x:xs)   ys
        _  -> x : merge cmp    xs (y:ys)


this function merges lists in pairs. rewriting it to make incremental
merging, using "sorted by first element" property and omitting finite
lists support, we get just: 

-- Merging infinite sorted lists
merge_lists :: (Ord a) => [[a]] -> [a]
merge_lists ((x:xs):xss) = x : merge xs (merge_lists xss)

merge :: (Ord a) => [a] -> [a] -> [a]
merge (x:xs) (y:ys)
 = case x > y of
        True -> y : merge (x:xs)   ys
        _    -> x : merge    xs (y:ys)


works for me with test script:

main = putStr (unlines$ map show$ merge_lists [[x*y | x<-[1..]]  |  y<-[1..]])

        




-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com