haskell heap sort

heap-sort.hs

import Data.List

swap :: Int -> Int -> [a] -> [a]
swap i j xs | i == j    = xs
swap i j xs | otherwise = initial ++ (xs !! b) : middle ++ (xs !! a) : end 
    where [a,b] = sort [i,j]
          initial = take a xs
          middle  = take (b-a-1) (drop (a+1) xs)
          end     = drop (b+1) xs

largest :: Ord a => Int -> Int -> [a] -> Int
largest i hs xs = 
        let large = if (l < hs) && ((xs !! l) > (xs !! i)) then l else i
        in if (r < hs) && ((xs !! r) > (xs !! large)) then r else large
        where l = 2 * i + 1
              r = 2 * i + 2

heapify :: Ord a => Int -> Int -> [a] -> [a]
heapify i hs xs = 
        if (large /= i) then heapify large hs (swap large i xs)
        else xs
        where large = largest i hs xs

buildheap :: Ord a => Int -> [a] -> [a]
buildheap 0 xs = heapify 0 (length xs) xs
buildheap i xs = buildheap (i - 1) (heapify i (length xs) xs)

hpsort i xs = let swapped = swap 0 i xs
              in if i /= 1 then hpsort (i - 1) (heapify 0 i swapped)
                 else (heapify 0 i swapped)

heapsort xs = let heap = buildheap (length xs `div` 2) xs
              in heapsorting (length xs - 1) heap

-- heapsort [16,4,10,14,7,9,3,2,8]

Yes, the array immutability makes it almost infeasible for a direct algorithm such as this to work. I read some of Chris Okasaki's work and I must confess it got me. Anyway, nice code indeed. There are some redundant guards though.