[Haskell-cafe] Computing a sorted list of products lazily
Bulat Ziganshin
bulat.ziganshin at gmail.com
Fri Apr 17 18:17:20 EDT 2009
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
More information about the Haskell-Cafe
mailing list