Haskell maxheapify

Question

I'm a Haskell beginner and trying to hone my skill by solving algorithmic problems. Here's what I got for maxheapify from Introduction to Algorithms

ixParent :: Int -> Int
ixParent = floor . flip (/) 2 . fromIntegral

ixLeft :: Int -> Int
ixLeft = (*) 2

ixRight :: Int -> Int
ixRight = (+) 1 . (*) 2

maxHeapify :: (Show a, Num a, Ord a) => Int -> [a] -> [a]
maxHeapify i h = if m == i then h else maxHeapify m h' where
  s = length h
  l = ixLeft i
  r = ixRight i
  m = snd $ maximumBy (\e1 e2-> compare (fst e1) (fst e2)) [(h!!(n-1), n)|n <- [i,l,r], n <= s]
  h' = h & ix (i-1) .~ (h!!(m-1)) & ix (m-1) .~ (h!!(i-1))

Any suggestions on the improvements or correction are highly appreciated. I'm looking for more idiomatic way of doing Haskell

Version 0.1:

import           Control.Lens
import           Data.List


ixP :: Int -> Int
ixP = floor . flip (/) 2 . fromIntegral

idxL :: Int -> Int
idxL = (*) 2

idxR :: Int -> Int
idxR = (+) 1 . (*) 2

maxHeapify ::(Ord a, Show a) => Int -> [a] -> [a]
maxHeapify _ [] = []
maxHeapify i h = if l == i then h else maxHeapify l h'
  where
    l = snd . maximumBy (\(i1,_) (i2,_) -> compare i1 i2)
      $ [(h!!(n-1), n) | n<- [i, idxL i, idxR i], n <= length h]
    h' = h
      & ix (i-1) .~ h!!(l-1)
      & ix (l-1) .~ h!!(i-1)

buildMaxHeap :: (Ord a, Show a) => [a] -> [a]
buildMaxHeap xs = go (ixP (length xs)) xs
  where
    go 0 xs = xs
    go i xs = go (i - 1) (maxHeapify i xs)

heapSort :: (Ord a, Show a) => [a] -> [a]
heapSort [] = []
heapSort h = heapSort (maxHeapify 1 xs) ++ [x]
 where
   mx = buildMaxHeap h
   x = head mx
   xs = tail mx

Update 1:

Added heapIncreaseKey

heapIncreaseKey :: (Ord a, Show a) => Int -> a -> [a] -> [a]
heapIncreaseKey i k h =
  if k < h!!(i-1)
  then fail "New Key is smaller than current one"
  else go i k h
  where
    go i k h = if i > 1 && h!!(p - 1) < k
      then go p k (h & ix (i-1) .~ h!!(p -1))
      else h & ix (i-1) .~ k
      where
        p = ixP i

Here my question is related to variable naming. I am using the same names for variables in the go function and the outer function. Is there a better way?

Answer 1

It's unusual to partially apply infix functions by first prefixing them, (*) 2 is equivalent to (2 *) and the latter is so much more common I can't recall ever even seeing the former. Note that you can also partially apply the second argument, as in (/ 2).

When you're using -By functions, a handy tool to have in your toolbox is the higher order function Data.Function.on :: (b -> b -> c) -> (a -> b) -> a -> a -> c. It allows you to project a digest function to work on any type you can derive its inputs from. E.g., maximumBy (compare `on` fst).

Your version \$0.1\$ I think does much better on readability, but you should be aware that you can pattern match on the left side of any assignment or bind. I.e. in heapSort, your entire where clause can be replaced by (x:xs) = buildMaxHeap h.

As to the rest, this just doesn't have the complexity of a typical heapsort. Haskell lists are linked lists, not arrays. Indexing, computing length, assigning elements and appending to the back ((++)) are all \$O(n)\$ operations. I think you might be able to write a version of heap sort with the right algorithmic complexity that is still pure using "array".Data.Array but it might involve tying the knot and I haven't put enough brain power to the task to say if it would really be possible. You could definitely do it with the vector package, having the escape hatch of working in ST.

---

Based on your “Update 1,” I'd definitely use names longer than a single letter. It all blends together visually, changing h to heap would probably help a lot, maybe changing k. I'm not sure “key” is really the term d'art either, aren't the things in a heap just called “values?” You could also use guards in the definition to condense it vertically a bit.

heapIncreaseKey i k h
  | k < h !! (i - 1) = error "..."
  | otherwise = go i k h
  where
    ...