Heap efficienti in lingue puramente funzionali

Question

Come esercizio in Haskell, sto cercando di implementare heapsort. L'heap viene solitamente implementato come una matrice in lingue imperative, ma questo sarebbe estremamente inefficiente nei linguaggi puramente funzionali. Quindi ho esaminato gli heap binari, ma tutto ciò che ho trovato finora li descrive da un punto di vista imperativo e gli algoritmi presentati sono difficili da tradurre in un'impostazione funzionale. Come implementare in modo efficiente un heap in un linguaggio puramente funzionale come Haskell?

Modifica: Per efficienza intendo che dovrebbe essere ancora in O (n * log n), ma non deve battere un programma C. Inoltre, mi piacerebbe usare la programmazione puramente funzionale. Che altro sarebbe il punto di farlo in Haskell?

Answer 1

Ci sono un certo numero di implementazioni di heap Haskell in un'appendice a Purely Functional Data Structures di Okasaki. (Il codice sorgente può essere scaricato al link. Il libro stesso vale la pena leggerlo.) Nessuno di essi è un heap binario, di per sé, ma lo "leftist" heap è molto simile. Ha O (log n) operazioni di inserimento, rimozione e unione. Esistono anche strutture dati più complicate come skew heaps, binomial heaps e splay heaps con prestazioni migliori.

Answer 2

Questa è una pagina contenente una versione ML di HeapSort. È abbastanza dettagliato e dovrebbe fornire un buon punto di partenza.

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

Answer 3

Proprio come in algoritmi efficienti quicksort scritto in Haskell, è necessario utilizzare monadi (trasformatori di stato) per fare cose sul posto.

Answer 4

È anche possibile utilizzare il monad ST, che consente di scrivere codice imperativo ma di esporre in modo sicuro un'interfaccia puramente funzionale.

Answer 5

Array a Haskell non sono così enormemente inefficiente come si potrebbe pensare, ma la pratica tipica in Haskell sarebbe probabilmente per implementare questo utilizzando i tipi di dati comuni, in questo modo:

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 

Se fossi soluzione di questo problema , Potrei iniziare inserendo gli elementi dell'elenco in una matrice, rendendo più semplice indicizzarli per la creazione dell'heap.

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

Se stai usando un max heap binario, si potrebbe desiderare di tenere traccia della dimensione del mucchio, come si rimuovono gli elementi in modo da poter trovare l'elemento in basso a destra in O (log N) tempo. Puoi anche dare un'occhiata ad altri tipi di heap che non sono in genere implementati usando matrici, come gli heap binomiali e gli heap di Fibonacci.

Una nota finale sulle prestazioni dell'array: in Haskell c'è un compromesso tra l'utilizzo di array statici e l'utilizzo di matrici mutevoli. Con gli array statici, è necessario creare nuove copie degli array quando si modificano gli elementi. Con gli array mutabili, il garbage collector ha difficoltà a tenere separate generazioni di oggetti. Prova ad implementare l'heapsort usando un STArray e vedi come ti piace.

Answer 6

Come esercizio in Haskell, ho implementato un heapsort imperativo con la Monad 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 

btw ho concorso che se non è puramente funzionale, allora non v'è alcun punto nel farlo in Haskell. Penso che la mia implementazione del giocattolo sia molto più bella di quella che si otterrebbe in C++ con i modelli, passando per le cose all'interno delle funzioni interne.

Answer 7

Jon Fairbairn inviato un heapsort funzionale alla mailing list Haskell Cafe nel 1997:

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

riproduco qui sotto, riformattato per adattarsi a questo spazio. Ho anche leggermente semplificato il codice di merge_heap.

Sono sorpreso che l'albero genealogico non è nel preludio standard poiché è così utile. Tradotto dalla versione che ho scritto in Ponder nell'ottobre 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) 

Answer 8

Ed ecco un Fibonacci Heap in Haskell:

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

Ecco il file pdf per qualche altro cumuli di k-ary basati sul lavoro di Okasaki.

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

Answer 9

Ho cercato di porta mucchio standard binario nelle impostazioni funzionali. C'è un articolo con l'idea descritta: A Functional Approach to Standard Binary Heaps. Tutti gli elenchi di codice sorgente nell'articolo sono in Scala. Ma potrebbe essere facilmente trasferito in qualsiasi altro linguaggio funzionale.