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@gmail.com