montes eficientes em linguagens puramente funcionais

Question

Como um exercício de Haskell, eu estou tentando implementar heapsort. A pilha é normalmente implementado como uma matriz em linguagens imperativas, mas isso seria altamente ineficiente em linguagens puramente funcionais. Então eu olhei para heaps binários, mas tudo o que eu encontrei até agora descreve-los do ponto de vista imperativo e os algoritmos apresentados são difíceis de traduzir para uma definição funcional. Como implementar de forma eficiente uma pilha em uma linguagem puramente funcional como Haskell?

Editar: Por eficiente Quero dizer que ainda deve estar em O (n * log n), mas ele não tem que bater um programa C. Além disso, eu gostaria de usar a programação puramente funcional. O que mais seria o ponto de fazê-lo em Haskell?

Answer 1

Há uma série de implementações de Haskell pilha em um apêndice Okasaki de Estruturas de dados puramente funcional . (O código fonte pode ser baixado no link. O livro em si é bem a pena a leitura.) Nenhum deles é heaps binários, por si só, mas o " esquerdista" amontoado é muito semelhante. Tem operações de O (N log N) para inserção, remoção, e de intercalação. Há também estruturas de dados mais complicadas, como inclinação montes , binomial montes e splay montões que têm melhor desempenho.

Answer 2

Jon Fairbairn colocaram um heapsort funcional para o Haskell Cafe mailing list em 1997:

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

Eu reproduzi-la abaixo, reformatado para caber neste espaço. Eu também ligeiramente simplificado o código de merge_heap.

Eu sou treefold surpreso não é no prelúdio padrão já que é tão útil. Traduzido a partir da versão que eu escrevi em Ponder em Outubro 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

Você também pode usar a Mônada ST, que permite escrever código imperativo, mas expor uma interface puramente funcional com segurança.

Answer 4

Como um exercício de Haskell, eu implementado um heapsort imperativo com o 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

concurso btw eu que se não é puramente funcional, então não há nenhum ponto em fazê-lo em Haskell. Eu acho que minha implementação brinquedo é muito mais agradável do que o que seria de alcançar em C ++ com modelos, passando em torno de coisas para as funções internas.

Answer 5

E aqui está uma pilha de Fibonacci em Haskell:

https: // github. com / liuxinyu95 / algoXY / blob / algoxy / datastruct / pilha / other-montes / src / FibonacciHeap.hs

Aqui estão o arquivo pdf para alguns outros montes k-ária com base no trabalho de Okasaki.

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

Answer 6

Assim como em algoritmos Quicksort eficientes escritos em Haskell, você precisa monads uso (transformadores estado) para fazer coisas no local.

Answer 7

Arrays em Haskell não são tão altamente ineficiente como se poderia pensar, mas a prática normal em Haskell seria provavelmente para implementar isso usando tipos de dados comuns, 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

Se eu fosse resolver este problema, eu poderia começar por encher os elementos da lista em uma matriz, tornando mais fácil para indexá-los para a criação heap.

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

Se você estiver usando uma pilha máximo binário, que você pode querer manter o controle do tamanho da pilha que você remover elementos para que você possa encontrar o elemento canto inferior direito em O (log n). Você também pode dar uma olhada em outros tipos de pilhas que não são normalmente implementadas usando matrizes, como montões binomial e montes de Fibonacci.

Uma nota final sobre o desempenho do array: em Haskell há uma troca entre usando matrizes estáticos e usando matrizes mutáveis. Com matrizes estáticas, você tem que criar novas cópias dos arrays quando você alterar os elementos. Com matrizes mutáveis, o coletor de lixo tem um tempo difícil manter diferentes gerações de objetos separados. Tente implementar o heapsort usando um starray e ver como você gosta dela.

Answer 8

Eu tentei porta heap binário padrão em configurações funcionais. Há um artigo com ideia descrito: uma abordagem funcional à Standard Binary Heaps . Todas as listagens de código fonte no artigo são em Scala. Mas pode ser portado muito fácil para qualquer outra língua funcional.

Answer 9

Aqui está uma página que contém uma versão ML de heapsort. É bastante detalhado e deve proporcionar um bom ponto de partida.

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