montones eficientes en lenguajes puramente funcionales

Question

A modo de ejercicio en Haskell, estoy tratando de implementar heapsort. La pila se implementa normalmente como una matriz en lenguajes imperativos, pero esto sería altamente ineficiente en lenguajes puramente funcionales. Así que he mirado montones binarios, pero todo lo encontrado hasta ahora los describe desde un punto de vista imprescindible y los algoritmos presentados son difíciles de traducir en un ambiente funcional. Cómo implementar eficazmente un montón en un lenguaje puramente funcional como Haskell?

Editar: Por eficientes que significa que todavía debe estar en O (n * log n), pero no tiene que vencer a un programa en C. Además, me gustaría utilizar la programación puramente funcional. ¿Qué otra cosa podría ser el punto de hacerlo en Haskell?

Answer 1

Hay un número de implementaciones de montón Haskell en un apéndice de Okasaki de Estructuras de datos puramente funcional . (El código fuente se puede descargar en el enlace. El libro en sí es bien vale la pena leer.) Ninguno de ellos son montones binarios, per se, pero el " izquierda" montón es muy similar. Tiene O (log n) de inserción, eliminación, y operaciones de combinación. También hay estructuras de datos más complicadas como skew montones , montones binomiales y href="http://en.wikipedia.org/wiki/Splay_heap" que tienen un mejor rendimiento.

Answer 2

Jon Fairbairn registró una heapsort funcional a la lista de correo Haskell Cafe en 1997:

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

Lo reproduzco a continuación, reformateado para adaptarse a este espacio. También he simplificado un poco el código de merge_heap.

  

Estoy sorprendido treefold no está en la antesala estándar ya que es muy útil. Traducido de la versión que escribí en Ponder en octubre de 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 3

También es posible usar la mónada ST, lo que le permite escribir código imperativo, sino exponer una interfaz puramente funcional con seguridad.

Answer 4

A modo de ejercicio en Haskell, que puso en marcha un heapsort imperativo con el ST Mónada.

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

I concurso que por cierto si no es puramente funcional, entonces no hay razón para hacerlo en Haskell. Creo que mi aplicación juguete es mucho mejor que lo que se podría lograr en C ++ con plantillas, que pasa alrededor de las cosas a las funciones internas.

Answer 5

Y aquí hay un montón de Fibonacci en Haskell:

https: // github. com / liuxinyu95 / algoXY / blob / algoxy / datastruct / montón / otro-montones / src / FibonacciHeap.hs

Aquí están los archivos PDF para algunos otros montones k-ario basado en la obra de Okasaki.

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

Answer 6

Al igual que en los algoritmos de ordenación rápida eficientes escrito en Haskell, es necesario utilizar mónadas (transformadores de estado) para hacer cosas en su lugar.

Answer 7

Las matrices en Haskell no son tan altamente ineficiente como se podría pensar, pero la práctica típica en Haskell, probablemente sería implementar esto utilizando tipos de datos comunes, como esto:

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

Si yo fuera la solución de este problema, que podría empezar por el relleno de los elementos de la lista en una matriz, por lo que es más fácil de ponerlos en un índice de creación de la pirámide.

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

Si estás usando un máximo de almacenamiento dinámico binario, es posible que desee realizar un seguimiento del tamaño del montón como de quitar los elementos para que pueda encontrar el elemento inferior derecha en O (log n). También puede tomar un vistazo a otros tipos de pilas que no se implementan normalmente utilizando matrices, como montones binomiales y montones de Fibonacci.

Una nota final sobre las prestaciones del sistema: en Haskell hay un equilibrio entre la utilización de matrices estáticas y utilizando matrices mutables. Con los arreglos estáticos, usted tiene que crear nuevas copias de las matrices cuando cambie los elementos. Con los arreglos mutables, el recolector de basura tiene dificultades para mantener diferentes generaciones de objetos separados. Intenta implementar el uso de un heapsort starray y ver cómo te gusta.

Answer 8

He intentado puerto pila binaria estándar en configuraciones funcionales. Hay un artículo con la idea descrita: un enfoque funcional de estándar binarios Montones . Todos los listados de código fuente en el artículo son en Scala. Pero podría ser portado muy fácil en cualquier otro lenguaje funcional.

Answer 9

Aquí hay una página que contiene una versión de ML HeapSort. Es bastante detallado y debe proporcionar un buen punto de partida.

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