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

Question

В качестве упражнения в Haskell я пытаюсь реализовать heapsort. Куча обычно реализуется как массив в императивных языках, но это было бы крайне неэффективно в чисто функциональных языках. Итак, я посмотрел на двоичные кучи, но все, что я нашел до сих пор, описывает их с обязательной точки зрения, и представленные алгоритмы трудно перевести на функциональную настройку. Как эффективно реализовать кучу на чисто функциональном языке, таком как Haskell?

Редактировать: Под эффективным я подразумеваю, что он все еще должен быть в O (n * log n), но он не должен побеждать программу на C Также я бы хотел использовать чисто функциональное программирование. Какой еще смысл делать это на Хаскеле?

Answer 1

В приложении к чисто функциональным структурам данных Okasaki имеется ряд реализаций кучи Haskell. (Исходный код можно скачать по ссылке. Саму книгу стоит прочитать.) По сути, ни одна из них не является двоичной кучей, но «левая» куча очень похожа. Он имеет O (log n) операции вставки, удаления и слияния. Существуют также более сложные структуры данных, такие как косые кучи , биномиальные кучи и splay heap , которые имеют лучшую производительность.

Answer 2

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

http://www.mail-archive.com/haskell@haskell.org/msg01788.html

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

Я удивлен, что древовидная структура не входит в стандартную прелюдию, поскольку она так полезна. В переводе с версии, которую я написал в «Ponder» в октябре 1992 года, «Джон Фэрбэрн

»

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)

Answer 3

Вы также можете использовать монаду ST, которая позволяет писать императивный код, но безопасно раскрывать чисто функциональный интерфейс.

Answer 4

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

{-# 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

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

Answer 5

А вот и куча Фибоначчи в Хаскеле:

https://github.com/liuxinyu95/AlgoXY/blob/algoxy/datastruct/heap/other-heaps/src/FibonacciHeap.hs

Вот pdf-файл для некоторых других куч, основанных на работе Окасаки.

https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf

Answer 6

Я попытался перенести стандартную двоичную кучу в функциональные настройки. Есть статья с описанной идеей: Функциональный подход к стандартным двоичным кучам . Все листинги исходного кода в статье в Scala. Но это может быть легко перенесено на любой другой функциональный язык.

Answer 7

Массивы в 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 существует компромисс между использованием статических массивов и изменяемых массивов. Со статическими массивами вы должны создавать новые копии массивов при изменении элементов. При использовании изменяемых массивов сборщику мусора трудно разделять объекты разных поколений. Попробуйте реализовать heapsort с помощью STArray и посмотрите, как вам это понравится.

Answer 8

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

Answer 9

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

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