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

Question

我一直在利用业余时间学习 Haskell LYAH .想通过解决命令式世界中的一些问题来提高我的 Haskell(/函数式编程)技能。 EPI 的问题之一是打印一个“almost sorted array”，以一种排序的方式，保证数组中没有元素与其正确位置的距离超过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，但是在这种情况我认为显式递归也相对可读。