Ben wrote: > a haskell newbie here, searching for comments and wisdom on my code. > > i had a project to try to implement "external sort" in haskell as a > learning exercise. (external sort is sorting a list that is too large > to fit in main memory, by sorting in chunks, spooling to disk, and > then merging. more properly there probably should be multiple stages, > but for simplicity i'm doing a one-stage external sort.) > > i'd appreciate any testing, comments and suggestions from the haskell > gods out there.
I'm not a god but I like it very much :) Especially because it's laziness in action. > blocks <- mapM (\x -> do {bs <- hGetContentsWithCursor h x; > return $ Bin.decode bs}) idx (Minuscule cosmetics: blocks <- mapM ((liftM Bin.decode) . hGetContentsWithCursor h) idx ) > Merging chunks. K-way merge (and in fact external sort in general) is > detailed in Knuth, where he recommends tournament trees. The easiest > thing is to probably use one of Okasaki's heaps. I'll use splay > heaps, because I don't know any better. > > It would be better if I changed Ord for blocks to only check the first > element. > >> kMerge :: (Ord a) => [[a]] -> [a] >> kMerge [] = [] >> kMerge l = >> let h = Splay.fromSeq l in >> kM (Splay.minElem h) (Splay.deleteMin h) >> where >> kM :: (Ord a) => [a] -> Splay.Heap [a] -> [a] >> kM l h >> | h == Splay.empty = l >> | otherwise = >> let next = Splay.minElem h >> (f, b) = span (\x -> x <= head next) l >> in >> f ++ (kM next (if null b then Splay.deleteMin h >> else (Splay.insert b $ Splay.deleteMin h))) >> >> kMergeSort :: (Ord a) => [a] -> [a] >> kMergeSort l = kMerge $ blockify blocksize l Oh, I would have expected a lazy mergesort here. Internally, this will work like a tournament heap. See also http://article.gmane.org/gmane.comp.lang.haskell.cafe/24180 Regards, apfelmus _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe