Эффективная "куча" на чисто функциональных языках

Как и в эффективных алгоритмах быстрой сортировки, написанных на Haskell, вам необходимо использовать монады (преобразователи состояний ), чтобы делать что-то на месте.

Массивы в Haskell не так уж и неэффективны, как вы думаете, но типичной практикой в ​​Haskell, вероятно, будет реализация этого с использованием обычных типов данных, например:

data Heap a = Empty | Heap a (Heap a) (Heap a)
fromList :: Ord a => [a] -> Heap a
toSortedList :: Ord a => Heap a -> [a]
heapSort = toSortedList . fromList

Если бы я решал Решив эту проблему, я мог бы начать с помещения элементов списка в массив, чтобы упростить их индексацию для создания кучи.

import Data.Array
fromList xs = heapify 0 where
  size = length xs
  elems = listArray (0, size - 1) xs :: Array Int a
  heapify n = ...

Если вы используете двоичную максимальную кучу, вы можете отслеживать размер кучи по мере удаления элементов, чтобы вы могли найти нижний правый элемент за время O (log N). Вы также можете взглянуть на другие типы куч, которые обычно не реализуются с использованием массивов, такие как биномиальные кучи и кучи Фибоначчи.

Последнее замечание о производительности массивов: в Haskell существует компромисс между использованием статических массивов и использованием изменяемых массивов . Со статическими массивами вы должны создавать новые копии массивов при изменении элементов. В случае изменяемых массивов сборщику мусора трудно разделить разные поколения объектов. Попробуйте реализовать динамическую сортировку с помощью STArray и посмотрите, как вам это понравится.

Вот страница, содержащая версию HeapSort для ML. Он довольно подробный и должен стать хорошей отправной точкой.

http://flint.cs.yale.edu/cs428/coq/doc/Reference-Manual021.html

You could also use the ST monad, which allows you to write imperative code but expose a purely functional interface safely.

В качестве упражнения на Haskell я реализовал императивную динамическую сортировку с помощью ST Monad.

{-# LANGUAGE ScopedTypeVariables #-}

import Control.Monad (forM, forM_)
import Control.Monad.ST (ST, runST)
import Data.Array.MArray (newListArray, readArray, writeArray)
import Data.Array.ST (STArray)
import Data.STRef (newSTRef, readSTRef, writeSTRef)

heapSort :: forall a. Ord a => [a] -> [a]
heapSort list = runST $ do
  let n = length list
  heap <- newListArray (1, n) list :: ST s (STArray s Int a)
  heapSizeRef <- newSTRef n
  let
    heapifyDown pos = do
      val <- readArray heap pos
      heapSize <- readSTRef heapSizeRef
      let children = filter (<= heapSize) [pos*2, pos*2+1]      
      childrenVals <- forM children $ \i -> do
        childVal <- readArray heap i
        return (childVal, i)
      let (minChildVal, minChildIdx) = minimum childrenVals
      if null children || val < minChildVal
        then return ()
        else do
          writeArray heap pos minChildVal
          writeArray heap minChildIdx val
          heapifyDown minChildIdx
    lastParent = n `div` 2
  forM_ [lastParent,lastParent-1..1] heapifyDown
  forM [n,n-1..1] $ \i -> do
    top <- readArray heap 1
    val <- readArray heap i
    writeArray heap 1 val
    writeSTRef heapSizeRef (i-1)
    heapifyDown 1
    return top

Между прочим, я оспариваю, что если это не чисто функционально, то нет смысл делать это в Haskell. Я думаю, что моя игрушечная реализация намного лучше, чем та, которую можно было бы достичь в C ++ с помощью шаблонов, передавая вещи внутренним функциям.

Джон Фэйрбэрн еще в 1997 году разместил функциональный хэппорт в списке рассылки Haskell Cafe:

_COPY10@haskell.org/msg01788.html

Я воспроизводю его ниже, переформатированный, чтобы вписать в это пространство. Я также слегка упростил код merge_heap.

Удивительно, что в стандартной прелюдии нет дерева, так как он так полезен. Переведено с версии, которую я написал в Ponder в октябре 1992 года -- Jon Fairbairn

module Treefold where

-- treefold (*) z [a,b,c,d,e,f] = (((a*b)*(c*d))*(e*f))
treefold f zero [] = zero
treefold f zero [x] = x
treefold f zero (a:b:l) = treefold f zero (f a b : pairfold l)
    where 
        pairfold (x:y:rest) = f x y : pairfold rest
        pairfold l = l -- here l will have fewer than 2 elements


module Heapsort where
import Treefold

data Heap a = Nil | Node a [Heap a]
heapify x = Node x []

heapsort :: Ord a => [a] -> [a]    
heapsort = flatten_heap . merge_heaps . map heapify    
    where 
        merge_heaps :: Ord a => [Heap a] -> Heap a
        merge_heaps = treefold merge_heap Nil

        flatten_heap Nil = []
        flatten_heap (Node x heaps) = x:flatten_heap (merge_heaps heaps)

        merge_heap heap Nil = heap
        merge_heap node_a@(Node a heaps_a) node_b@(Node b heaps_b)
            | a < b = Node a (node_b: heaps_a)
            | otherwise = Node b (node_a: heaps_b)