أكوام فعالة في لغات وظيفية بحتة

Question

كممارسة في Haskell، أحاول تنفيذ HeApsort. عادة ما يتم تنفيذ الكومة كصفيف في لغات حتمية، ولكن هذا سيكون غير فعال للغاية باللغات الوظيفية البحتة. لذلك نظرت إلى أكوام ثنائية، ولكن كل ما وجدته حتى الآن يصفها من وجهة نظر حتمية ويصعب ترجمة الخوارزميات المقدمة إلى إعداد وظيفي. كيفية تنفيذ كومة بكفاءة في لغة وظيفية بحتة مثل Haskell؟

يحرر: من خلال كفاءة أعني أنه لا يزال ينبغي أن يكون في O (n * log n)، لكن لا يتعين عليه التغلب على برنامج ج. أيضا، أود استخدام البرمجة الوظيفية بحتة. ماذا سيكون نقطة القيام بذلك في هاسكل؟

Answer 1

هناك عدد من تطبيقات Haskell Heap في الملحق إلى Okasaki هياكل البيانات الوظيفية البحتة. وبعد (يمكن تنزيل شفرة المصدر على الرابط. الكتاب نفسه يستحق القراءة.) لا أحد منهم أكوام ثنائية، في حد ذاتها، ولكن كومة "اليساري" متشابه كثيرا. لديها o (سجل n) الإدراج، والإزالة، ودمج العمليات. هناك أيضا هياكل بيانات أكثر تعقيدا مثل أكوام الانحراف, أكوام binomial, ، و جوبيد أكوام التي لها أداء أفضل.

Answer 2

نشر جون فيربيرن إيفسورت وظيفي إلى القائمة البريدية في Haskell Cafe مرة أخرى في عام 1997:

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

أنا إعادة إنتاجها أدناه، إعادة تهيئة لتناسب هذه المساحة. أنا أيضا تبسيط رمز MERGE_HEAP قليلا.

أنا مندهشا ليس في مقدمة قياسية لأنه مفيد للغاية. ترجم من النسخة كتبت في التأمل في أكتوبر 1992 - جون فيربيرن

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

يمكنك أيضا استخدام ST مناد، الذي يسمح لك بكتابة رمز حتمي ولكنه يعرض واجهة وظيفية بحتة بأمان.

Answer 4

كممارسة في Haskell، قمت بتنفيذ ميناء حتمي مع سانت موناد.

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

راجع للشغل أنا مسابقة أنه إذا لم تكن وظيفية بحتة، فلا توجد نقطة في القيام بذلك في Haskell. أعتقد أن تطبيق لعبتي أجمل بكثير مما يحققه المرء في C ++ مع قوالب، ويمر حول الاشياء إلى الوظائف الداخلية.

Answer 5

وهنا هو كومة فيبوناتشي في هاسكل:

https://github.com/liuxinyu95/algoxy/Blob/algoxy/algoxy/datasrent/heap/other-heaps/src/fibonacciap.hs.

فيما يلي ملف PDF لبعض أكوام K-ARY الأخرى بناء على عمل Okasaki.

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

Answer 6

تماما مثل في خوارزميات QuickSort فعالة مكتوبة في Haskell، تحتاج إلى استخدام Monads (محولات الدولة) للقيام بالأشياء في مكانها.

Answer 7

المصفوفات في Haskell ليست غير فعالة بشكل كبير حيث قد تفكر، لكن الممارسة النموذجية في Haskell ستكون تنفيذ هذا باستخدام أنواع البيانات العادية، مثل هذا:

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

إذا كنت قد قمت بحل هذه المشكلة، فقد أبدأ بحشو عناصر القائمة إلى صفيف، مما يسهل فهرسة خصيصا لإنشاء كومة الكومة.

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

إذا كنت تستخدم كومة أقصى ثنائية، فقد ترغب في تتبع حجم كومة الكومة أثناء إزالة العناصر حتى تتمكن من العثور على العنصر الأيمن السفلي في وقت O (سجل N). يمكنك أيضا إلقاء نظرة على أنواع أخرى من أكوام غير المنفذة عادة باستخدام صفائف، مثل أكوام binomial وأكواك fibonacci.

ملاحظة نهائية على أداء الصفيف: في Haskell هناك مفاضلة بين استخدام صفائف ثابتة واستخدام صفائف قابل للتغيير. مع صفائف ثابتة، يجب عليك إنشاء نسخ جديدة من الصفائف عند تغيير العناصر. مع صفائف متغيرة، يحتوي جامع القمامة على صعوبة في الحفاظ على أجيال مختلفة من الكائنات المنفصلة. حاول تنفيذ HeApSort باستخدام Starray ونرى كيف تريد ذلك.

Answer 8

حاولت ميناء الكومة الثنائية القياسية في الإعدادات الوظيفية. هناك مقال مع فكرة موصوفة: نهج وظيفي في أكوام الثنائية القياسية. وبعد جميع قوائم شفويات المصدر في المقالة موجودة في Scala. ولكن قد يكون من السهل جدا في أي لغة وظيفية أخرى.

Answer 9

فيما يلي صفحة تحتوي على إصدار ML من Heapsort. انها مفصلة تماما وينبغي أن توفر نقطة انطلاق جيدة.

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