Haskell:对几乎排序的数组进行排序

Question

我在业余时间通过LYAH学习Haskell .想通过解决命令式世界中的一些问题来改进我的Haskell(/ Functional编程)技能.EPI的一个问题是以排序的方式打印" 几乎排序的数组 ",其中保证数组中的元素不超过k其正确位置.输入是元素流,并且要求在O(n log k)时间复杂度和O(k)空间复杂性方面做到这一点.

我试图在Haskell中重新实现命令式解决方案,如下所示:

import qualified Data.Heap as Heap

    -- print the k-sorted list in a sorted fashion
ksorted :: (Ord a, Show a) => [a] -> Int -> IO ()
ksorted [] _ = return ()
ksorted xs k = do 
    heap <- ksorted' xs Heap.empty
    mapM_ print $ (Heap.toAscList heap) -- print the remaining elements in the heap.
    where 
        ksorted' :: (Ord a, Show a) => [a] -> Heap.MinHeap a -> IO (Heap.MinHeap a)
        ksorted' [] h = return h
        ksorted' (x:xs) h = do let (m, h') = getMinAndBuildHeap h x in
                                (printMin m >> ksorted' xs h')

        printMin :: (Show a) => Maybe a -> IO ()
        printMin m = case m of 
                        Nothing     -> return ()
                        (Just item) -> print item

        getMinAndBuildHeap :: (Ord a, Show a) => Heap.MinHeap a -> a -> (Maybe a, Heap.MinHeap a)
        getMinAndBuildHeap h item= if (Heap.size h) > k 
                                   then ((Heap.viewHead h), (Heap.insert item (Heap.drop 1 h)))
                                   else (Nothing, (Heap.insert item h))

我想知道在Haskell中解决这个问题的更好方法.任何输入将不胜感激.

[编辑1]:输入是流,但是现在我假设了一个列表(在某种意义上只有一个正向迭代器/输入迭代器.)

[编辑2]:Data.Heap为代码添加了导入.

谢谢.

Answer 1

我认为主要的改进是将排序列表的生成与排序列表的打印分开.所以:

import Data.Heap (MinHeap)
import qualified Data.Heap as Heap

ksort :: Ord a => Int -> [a] -> [a]
ksort k xs = go (Heap.fromList b) e where
    (b, e) = splitAt (k-1) xs

    go :: Ord a => MinHeap a -> [a] -> [a]
    go heap [] = Heap.toAscList heap
    go heap (x:xs) = x' : go heap' xs where
        Just (x', heap') = Heap.view (Heap.insert x heap)

printKSorted :: (Ord a, Show a) => Int -> [a] -> IO ()
printKSorted k xs = mapM_ print (ksort k xs)

如果我感觉特别喜欢,我可能会尝试go变成一个foldr或者可能是一个mapAccumR,但在这种情况下,我认为显式递归也是相对可读的.