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]

Hi. Nice code! I am reading "Introduction to Algorithms" and trying to write algorithms on haskell. I reached to heapsort and got a troubles. It is very imperative. So I wanted to say: your decision is done correctly according to the algorithm, but it is not effective. You know swap, take, drop, ++ it is all works for O(n). heapsort ([1..10000]):
"sample.hs: out of memory
[Finished in 138.6s with exit code 1]"

possible solutions

1. read Okasaki's Purely Functional Data Structures (advice from SO)
2. use ST Array monad.
3. realise heap as tree, not list. It's wrong but it's easier and clearer and faster.
   I'll try 3d
   PS Also on 33 line heapsorting -> hpsort

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.