Effiziente Haufen in rein funktionalen Sprachen

Question

Als Übung in Haskell, ich versuche Heapsort zu implementieren. Der Haufen ist in der Regel als ein Array in imperativen Sprachen implementiert, aber dies würde in rein funktionalen Sprachen äußerst ineffizient. Also habe ich auf binäre Haufen sah, aber alles, was ich bisher gefunden beschreibt sie von einer imperativen Sicht und die vorgestellten Algorithmen sind nur schwer zu einem funktionalen Rahmen zu übersetzen. Wie effizient einen Haufen in einer rein funktionalen Sprache wie Haskell implementieren?

Edit: Mit dem effizienten meine ich es noch in O (n * log n) sein sollte, aber es muss nicht ein C-Programm schlagen. Außerdem würde Ich mag rein funktionale Programmierung verwenden. Was sonst wäre der Punkt davon in Haskell zu tun?

Answer 1

Es gibt eine Reihe von Haskell Heap-Implementierungen in einem Anhang zu Okasaki des rein funktionale Datenstrukturen . (Der Quellcode kann über den Link heruntergeladen werden. Das Buch selbst wert ist zu lesen.) Keiner von ihnen binäre Haufen sind, per se, aber die " linker“heap ist sehr ähnlich. Es hat O (log n) Einsetzen, Entfernen und Operationen verschmelzen. Darüber hinaus gibt es noch komplizierte Datenstrukturen wie Skew Heaps , binomischen Haufen und spreizen Haufen , die haben eine bessere Leistung.

Answer 2

Jon Fairbairn eine funktionelle Heapsort zur Haskell Cafe Mailingliste im Jahr 1997:

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

Ich gebe es unten, neu formatiert, diesen Raum zu passen. Ich habe auch den Code von merge_heap etwas vereinfacht.

  

Ich bin überrascht, treefold ist in dem Standard-Auftakt nicht, da es so nützlich ist. Übersetzt aus der Version, die ich in Ponder im Oktober 1992 schrieb - 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 3

Sie können auch die ST Monade verwenden, die Sie sicher zwingend notwendig, Code zu schreiben, aber belichten eine rein funktionale Schnittstelle erlaubt.

Answer 4

Als Übung in Haskell, ich implementiert einen dringend notwendigen Heapsort mit dem 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

btw, dass ich anfechten, wenn sie nicht rein funktional ist dann keinen Sinn, da dabei in Haskell ist. Ich glaube, mein Spielzeug Umsetzung ist viel schöner als das, was man in C ++ mit Vorlagen erzielen würde, um Sachen zu den inneren Funktionen übergeben.

Answer 5

Und hier ist ein Fibonacci-Heap in Haskell:

https: // GitHub. com / liuxinyu95 / algoXY / Blob / algoxy / datastruct / Haufen / andere Haufen / src / FibonacciHeap.hs

Hier sind die pdf-Datei für einige anderen k-ary Haufen basierend auf Okasaki Arbeit.

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

Answer 6

Genau wie in effizientem Quicksort Algorithmen in Haskell geschrieben, müssen Sie Monaden (state Transformatoren) zu tun Sachen an Ort und Stelle verwendet werden.

Answer 7

Arrays in Haskell sind nicht so extrem ineffizient, wie Sie vielleicht denken, aber typische Praxis in Haskell würde wahrscheinlich dies mit normalen Datentypen zu implementieren sein, wie folgt:

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

Wenn ich dieses Problem zu lösen war, könnte ich durch Füllung der Listenelemente in ein Array starten, es leichter zu indizieren sie für die Halde Schöpfung zu machen.

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

Wenn Sie eine binäre max Heap verwenden, könnte man den Überblick über die Größe des Haufens halten wollen, wie Sie Elemente entfernen, so dass Sie die rechte untere Element in O finden (log N) Zeit. Sie könnten auch einen Blick auf andere Arten von Haufen nehmen, die nicht typischerweise Arrays implementiert, wie binomische Haufen und Fibonacci-Heaps.

Eine letzte Anmerkung auf Array-Leistung: in Haskell es ein Kompromiss ist statischen Arrays zwischen der Verwendung änderbare Arrays. Mit statischen Arrays, müssen Sie neue Kopien der Arrays erstellen, wenn Sie die Elemente ändern. Mit veränderlichem Arrays hat der Garbage-Collector schwer halten verschiedene Generationen von getrennten Objekten. Versuchen Sie die Umsetzung des Heapsort eine starray und sehen, wie es Ihnen gefällt.

Answer 8

Ich habe versucht, in den Hafen Standardbinärdistributionen Heap in Funktionseinstellungen. Es gibt einen Artikel mit dem beschriebenen Idee: einem Funktionsansatz zum Standard-Binary Heaps . Alle Quellcode Inserate in dem Artikel sind in Scala. Aber es könnte sehr leicht in jede andere funktionale Sprache portiert werden.

Answer 9

Hier ist eine Seite eine ML-Version von HeapSort enthält. Es ist ziemlich detailliert und soll einen guten Ausgangspunkt bieten.

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