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

• daydaynatation: Thank you very much for your review! I've updated a new function. I have some doubts on the naming of variables and also on the use of fail. Could you comment?
• daydaynatation: I am aware of the performance issues with Data.List. But the APIs for List is cleaner compared to the other packages. And this is definitely not production code. But really appreciate your thoughtful hints!
• daydaynatation: BTW, do you mean Data.Vector.Mutable? I am seeing quite a number of vector sub-modules
• bisserlis: I can provide a more thorough review on your update later, but I think you're looking for error, not fail. fail in the list monad will just return [] as far as I recall. error crashes the program. Maybe you'd like to use Either String [a] in the return type of the function? There are a bunch of different flavors of vector, yeah. Since you're working on collections of unknown elements ((Ord a, Show a) => a being all you know) then yeah, Data.Vector.Mutable. If you knew more about the type you could take advantage of Unboxed or Storable for a more space-efficient vector.