Haskell maxheapify

Я новичок в Haskell и пытаюсь отточить свои навыки, решая алгоритмические задачи. Вот что у меня есть для maxheapify из 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))

Мы высоко ценим любые предложения по улучшению или исправлению. Я ищу более идиоматический способ работы с Haskell

Версия 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

Обновление 1:

Добавлен 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

Здесь мой вопрос связан с именованием переменных. Я использую те же имена для переменных в go функция и внешняя функция. Есть ли способ лучше?

Необычно частично применять инфиксные функции, предварительно добавляя к ним префикс, (*) 2 эквивалентно (2 *) и последнее настолько распространено, что я не припомню, чтобы когда-либо видел первое. Обратите внимание, что вы также можете частично применить второй аргумент, как в (/ 2).

Когда вы используете -By функции, удобный инструмент, который должен быть в вашем наборе инструментов, — это функция высшего порядка Data.Function.on :: (b -> b -> c) -> (a -> b) -> a -> a -> c. Он позволяет вам спроектировать функцию дайджеста для работы с любым типом, из которого вы можете получить ее входные данные. Например, maximumBy (compare `on` fst).

Ваша версия $ 0.1 $ Я думаю, он намного лучше читается, но вы должны знать, что вы можете сопоставить с образцом слева от любого присваивания или привязки. Т.е. в heapSort, весь ваш пункт where можно заменить на (x:xs) = buildMaxHeap h.

Что касается остального, то здесь просто нет сложности типичной кучной сортировки. Списки Haskell — это связанные списки, а не массивы. Индексирование, вычисление длины, присвоение элементов и добавление в конец ((++)) являются все $ O (п) $ операции. я считать вы могли бы написать версию сортировки кучи с правильной алгоритмической сложностью, которая все еще остается чистой, используя "array".Data.Array но это может быть связано с тем, чтобы связать себя узами брака, а у меня недостаточно мозговых сил для выполнения этой задачи, чтобы сказать, действительно ли это возможно. Вы определенно могли бы сделать это с помощью векторного пакета, имея аварийный выход для работы в ST.