tas efficaces dans les langues purement fonctionnels

Question

Comme un exercice de Haskell, je suis en train de mettre en œuvre heapsort. Le tas est généralement mis en œuvre comme un tableau dans les langues impératives, mais ce serait extrêmement inefficace dans les langues purement fonctionnelles. J'ai donc regardé des tas binaires, mais tout ce que je trouve jusqu'à présent les décrit d'un point de vue impératif et les algorithmes présentés sont difficiles à traduire dans un cadre fonctionnel. Comment mettre en œuvre efficacement un tas dans un langage purement fonctionnel tel que Haskell?

Edit: Par efficace, je veux dire qu'il devrait encore être en O (n log n *), mais il ne doit pas battre un programme C. De plus, je voudrais utiliser la programmation purement fonctionnelle. Que d'autre serait le point de le faire dans Haskell?

Answer 1

Il y a un certain nombre d'implémentations de tas Haskell dans une annexe à Okasaki purement Structures de données fonctionnelles . (Le code source peut être téléchargé sur le lien. Le livre lui-même est digne d'être lue.) Aucun d'entre eux sont des tas binaires, en soi, mais le " gauchiste » est très similaire. Il a l'insertion O (log n), la suppression et la fusion des opérations. Il existe également des structures de données plus complexes comme biais des tas , tas binomial , et tas ébrasés qui ont de meilleures performances.

Answer 2

Jon Fairbairn a affiché une heapsort fonctionnelle à la liste de diffusion Café Haskell en 1997:

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

Je reproduis ci-dessous, reformaté pour adapter cet espace. Je suis aussi un peu simplifié le code de merge_heap.

  

Je suis surpris treefold est pas le prélude norme car il est si utile. Traduit de la version que j'ai écrit en Ponder en Octobre 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

Vous pouvez également utiliser la monade ST, qui vous permet d'écrire du code impératif, mais exposer une interface purement fonctionnelle en toute sécurité.

Answer 4

Comme un exercice de Haskell, je mis en œuvre un heapsort impératif avec le 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 je conteste que si ce n'est pas alors purement fonctionnel, il est inutile de le faire dans Haskell. Je pense que ma mise en œuvre du jouet est beaucoup plus agréable que ce que l'on atteindraient en C ++ avec des modèles, en passant autour de choses aux fonctions internes.

Answer 5

Et voici un Fibonacci Heap dans Haskell:

https: // GitHub. com / liuxinyu95 / algoXY / blob / algoxy / datastruct / tas / autre-tas / src / FibonacciHeap.hs

Voici le fichier pdf pour d'autres tas de k-aire sur la base du travail de Okasaki.

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

Answer 6

Tout comme dans les algorithmes QuickSort efficaces écrits en Haskell, vous devez utiliser monades (transformateurs de l'État) pour faire des choses en place.

Answer 7

Les tableaux dans Haskell ne sont pas aussi extrêmement inefficace que vous pourriez penser, mais la pratique typique dans Haskell serait probablement de mettre en œuvre ce en utilisant les types de données ordinaires, comme ceci:

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 je résoudre ce problème, je pourrais commencer par bourrer les éléments de la liste dans un tableau, ce qui rend plus facile de les indexer pour la création de tas.

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

Si vous utilisez un tas max binaire, vous pouvez garder une trace de la taille du tas que vous supprimez des éléments afin que vous puissiez trouver l'élément en bas à droite dans O (log N) temps. Vous pouvez également jeter un oeil à d'autres types de tas qui ne sont généralement pas mises en œuvre en utilisant des tableaux, comme des tas et des tas binomial fibonacci.

Une note finale sur les performances du tableau: dans Haskell il y a un compromis entre l'utilisation de tableaux statiques et en utilisant des tableaux mutables. Avec les tableaux statiques, vous devez créer de nouvelles copies des tableaux lorsque vous modifiez les éléments. Avec des tableaux mutables, le collecteur des ordures a du mal à garder les différentes générations d'objets séparés. Essayez mise en œuvre du heapsort en utilisant un starray et apprenez comment vous le souhaitez.

Answer 8

J'ai essayé de tas binaire de port standard dans les paramètres fonctionnels. Il y a un article décrit idée: une approche fonctionnelle standard binaire Heaps. Toutes les annonces de code source dans l'article sont en Scala. Mais il peut être porté très facile dans une autre langue fonctionnelle.

Answer 9

Voici une page contenant une version ML de HeapSort. Il est assez détaillé et devrait fournir un bon point de départ.

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