mucchi efficienti in lingue puramente funzionali

StackOverflow https://stackoverflow.com/questions/932721

Domanda

Come un esercizio di Haskell, sto cercando di implementare Heapsort. Il mucchio di solito è implementato come un array in linguaggi imperativi, ma questo sarebbe estremamente inefficiente in linguaggi puramente funzionali. Così ho guardato cumuli binari, ma tutto quello che ho trovato finora li descrive dal punto di vista fondamentale e gli algoritmi presentati sono difficili da tradurre in un ambiente funzionale. Come implementare in modo efficiente un mucchio in un linguaggio puramente funzionale come Haskell?

Modifica: Con efficiente voglio dire che dovrebbe essere ancora in O (n * log n), ma non ha bisogno di battere un programma C. Inoltre, mi piacerebbe usare programmazione puramente funzionale. Che altro sarebbe il punto di farlo in Haskell?

È stato utile?

Soluzione

Ci sono una serie di implementazioni Haskell heap in appendice al Okasaki di puramente funzionale Strutture dati . (Il codice sorgente può essere scaricato al link. Il libro stesso è ben la pena di leggere.) Nessuno di loro sono cumuli binari, di per sé, ma il " di sinistra" mucchio è molto simile. Ha O (log n) di inserimento, cancellazione, e operazioni di unione. Ci sono anche strutture dati più complesse, come skew cumuli , cumuli binomio , e cumuli strombatura che avere prestazioni migliori.

Altri suggerimenti

Jon Fairbairn ha registrato 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 un po 'semplificato il codice di merge_heap.

  

Sono treefold sorpreso non è nel preludio di serie dal momento che è 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)

Si potrebbe anche usare la monade ST, che permette di scrivere codice imperativo, ma esporre un'interfaccia puramente funzionale in modo sicuro.

Come un esercizio di Haskell, ho implementato un heapsort imperativo con la ST Monade. 

{-# 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. Credo che la mia implementazione giocattolo è molto più bello di quello che ci si ottenere in C ++ con i modelli, passando intorno roba per le funzioni interne.

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

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 io fossi la soluzione di questo problema, potrei iniziare da ripieno gli elementi della lista in un array, rendendo più facile per indicizzarli per la creazione di 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. Si potrebbe anche dare un'occhiata in altri tipi di cumuli che non sono tipicamente implementate utilizzando gli array, come mucchi binomiali e cumuli di Fibonacci.

Una nota finale sulle prestazioni dell'array: in Haskell c'è un compromesso tra l'utilizzo di matrici statiche e usando array mutevoli. Con gli array statici, è necessario creare nuove copie di array quando si modificano gli elementi. Con gli array mutevoli, il garbage collector ha difficoltà a tenere diverse generazioni di oggetti separati. Provate l'attuazione del heapsort utilizzando uno STArray e vedere come ti piace.

Ho cercato di porto heap binario di serie nelle impostazioni funzionali. C'è un articolo con l'idea descritta: un approccio funzionale alla standard binario Heaps . Tutti gli annunci di codice sorgente in questo articolo sono a Scala. Ma potrebbe essere portato molto facile in qualsiasi altra lingua funzionale.

Questa è una pagina contenente una versione ML di Heapsort. E 'abbastanza dettagliato e dovrebbe fornire un buon punto di partenza.

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

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top