haskell functional-programming binary-heap heapsort purely-functional

haskell - Montones eficientes en idiomas puramente funcionales



functional-programming binary-heap (9)

Al igual que en los algoritmos eficientes de Quicksort escritos en Haskell, debe usar mónadas (transformadores de estado) para hacer las cosas en su lugar.

Como ejercicio en Haskell, estoy tratando de implementar heapsort. El montón generalmente se implementa como una matriz en lenguajes imperativos, pero esto sería enormemente ineficiente en lenguajes puramente funcionales. Así que he visto montones binarios, pero todo lo que he encontrado hasta ahora los describe desde un punto de vista imperativo y los algoritmos presentados son difíciles de traducir a una configuración funcional. ¿Cómo implementar eficientemente un montón en un lenguaje puramente funcional como Haskell?

Editar: Por eficiente quiero decir que todavía debería estar en O (n * log n), pero no tiene que vencer a un programa C. Además, me gustaría usar programación puramente funcional. ¿Qué otra cosa sería el sentido de hacerlo en Haskell?

Como ejercicio en Haskell, implementé un heapsort imperativo con 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

Por cierto, impugnar que si no es puramente funcional, entonces no tiene sentido hacerlo en Haskell. Creo que la implementación de mi juguete es mucho más agradable de lo que se lograría en C ++ con plantillas, pasando cosas a las funciones internas.

Hay una serie de implementaciones de Heap de Haskell en un apéndice de las Estructuras de datos puramente funcionales de Okasaki. (El código fuente se puede descargar en el enlace. Vale la pena leer el libro en sí). Ninguno de ellos son montones binarios, per se, pero el montón "izquierdista" es muy similar. Tiene operaciones de inserción, eliminación y fusión O (log n). También hay estructuras de datos más complicadas como montones oblicuos , montones binomiales y montículos de separación que tienen un mejor rendimiento.

Jon Fairbairn publicó un heapsort funcional en la lista de correo de Haskell Cafe en 1997:

http://www.mail-archive.com/[email protected]/msg01788.html

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

Me sorprende que Treefold no esté en el preludio 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)

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

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 estuviera resolviendo este problema, podría comenzar rellenando los elementos de la lista en una matriz, facilitando su indexación para la creación de heap.

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

Si está utilizando un montón máximo binario, es posible que desee realizar un seguimiento del tamaño del montón a medida que elimina elementos para poder encontrar el elemento inferior derecho en el tiempo O (registrar N). También podría echar un vistazo a otros tipos de montones que normalmente no se implementan mediante matrices, como montones binomiales y montones de fibonacci.

Una nota final sobre el rendimiento de la matriz: en Haskell hay una compensación entre el uso de matrices estáticas y el uso de matrices mutables. Con las matrices estáticas, debe crear nuevas copias de las matrices cuando cambie los elementos. Con las matrices mutables, el recolector de basura tiene dificultades para mantener diferentes generaciones de objetos separados. Intente implementar heapsort utilizando una STArray y vea cómo le gusta.

También puede usar la mónada ST , que le permite escribir un código imperativo pero exponer de manera segura una interfaz puramente funcional.

Traté de portar el montón binario estándar en la configuración funcional. Hay un artículo con la idea descrita: Un enfoque funcional para las pilas binarias estándar . Todos los listados de código fuente en el artículo están en Scala. Pero podría portarse muy fácilmente en cualquier otro lenguaje funcional.