CODEWITHSUNDEEP
algorithmsortinghaskell
user3169543
user3169543

Reputation: 1589

Haskell: Sort an almost-sorted array

I've been learning Haskell in my spare time working through LYAH. Would like to improve upon my Haskell (/ Functional programming) skills by solving some problems from the imperative world. One of the problems from EPI is to print an "almost sorted array", in a sorted fashion where it is guaranteed that no element in the array is more than k away from its correct position. The input is a stream of elements and the requirement is to do this in O(n log k) time complexity and O(k) space complexity.

I've attempted to re-implement the imperative solution in Haskell as follows:

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))

I would like to know a better way of solving this in Haskell. Any inputs would be appreciated.

[Edit 1]: The input is stream, but for now I assumed a list instead (with only a forward iterator/ input iterator in some sense.)

[Edit 2]: added Data.Heap import to the code.

Thanks.

Upvotes: 0

Views: 273

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 152707

I think the main improvement is to separate the production of the sorted list from the printing of the sorted list. So:

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)

If I were feeling extra-special-fancy, I might try to turn go into a foldr or perhaps a mapAccumR, but in this case I think the explicit recursion is relatively readable, too.

Upvotes: 5

Related Questions