haskell update विशुद्ध रूप से कार्यात्मक भाषाओं में कुशल ढेर

latest election news in india (8)

हास्केल में ऐरे उतने अयोग्य नहीं हैं जितना आप सोच सकते हैं, लेकिन हास्केल में विशिष्ट अभ्यास शायद इस तरह से साधारण डेटा प्रकारों का उपयोग करके इसे लागू करना होगा:

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 (लॉग एन) समय में नीचे सही तत्व पा सकें। आप अन्य प्रकार के ढेर पर भी नज़र डाल सकते हैं जो आमतौर पर ऐरे का उपयोग करके कार्यान्वित नहीं होते हैं, जैसे कि बिनोमियल हीप्स और रिट्रेसमेंट हीप्स।

सरणी प्रदर्शन पर एक अंतिम नोट: हास्केल में स्थिर सरणियों का उपयोग करने और उत्परिवर्ती सरणियों का उपयोग करने के बीच एक व्यापार है। स्थैतिक सरणियों के साथ, आपको तत्वों को बदलते समय सरणियों की नई प्रतियां बनानी होंगी। परिवर्तनशील सरणियों के साथ, कचरा संग्रहकर्ता के पास अलग-अलग पीढ़ियों की वस्तुओं को अलग रखने के लिए एक कठिन समय होता है। एक STArray का उपयोग करके गति को लागू करने का प्रयास करें और देखें कि आपको यह कैसे पसंद है।

हास्केल में एक अभ्यास के रूप में, मैं हेस्पोर्ट को लागू करने की कोशिश कर रहा हूं। ढेर आमतौर पर अनिवार्य भाषाओं में एक सरणी के रूप में लागू किया जाता है, लेकिन यह विशुद्ध रूप से कार्यात्मक भाषाओं में बेहद अक्षम होगा। इसलिए मैंने बाइनरी हीप को देखा है, लेकिन अब तक मुझे जो कुछ भी मिला है वह उन्हें एक अनिवार्य दृष्टिकोण से वर्णन करता है और प्रस्तुत एल्गोरिदम एक कार्यात्मक सेटिंग में अनुवाद करना मुश्किल है। हस्केल जैसे विशुद्ध रूप से कार्यात्मक भाषा में ढेर को कुशलतापूर्वक कैसे लागू किया जाए?

संपादित करें: कुशल से मेरा मतलब है कि यह अभी भी ओ (एन * लॉग एन) में होना चाहिए, लेकिन इसमें सी प्रोग्राम को हरा नहीं है। इसके अलावा, मैं विशुद्ध रूप से कार्यात्मक प्रोग्रामिंग का उपयोग करना चाहूंगा। हास्केल में इसे करने का और क्या मतलब होगा?

और यहाँ हास्केल में एक फिबोनाची ढेर है:

https://github.com/liuxinyu95/AlgoXY/blob/algoxy/datastruct/heap/other-heaps/src/FibonacciHeap.hs

ओकासाकी के काम के आधार पर कुछ अन्य के-ऐरी ढेर के लिए पीडीएफ फाइल यहां दी गई है।

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

मैंने कार्यात्मक सेटिंग्स में मानक बाइनरी हीप को पोर्ट करने की कोशिश की। वर्णित विचार के साथ एक लेख है: मानक बाइनरी हीप्स के लिए एक कार्यात्मक दृष्टिकोण । लेख के सभी स्रोत कोड सूची स्काला में हैं। लेकिन यह किसी भी अन्य कार्यात्मक भाषा में बहुत आसान हो सकता है।

ओकासाकी के विशुद्ध रूप से कार्यात्मक डेटा संरचनाओं के लिए परिशिष्ट में कई हस्केल हीप कार्यान्वयन हैं। (स्रोत कोड लिंक पर डाउनलोड किया जा सकता है। पुस्तक स्वयं पढ़ने लायक है।) उनमें से कोई भी द्विआधारी ढेर नहीं है, प्रति se, लेकिन "वामपंथी" ढेर समान है। इसमें ओ (लॉग एन) सम्मिलन, हटाने और मर्ज संचालन है। अधिक जटिल डेटा संरचनाएं भी हैं जैसे कि तिरछा ढेर , द्विपद हीप्स और स्प्ले हीप्स जिनमें बेहतर प्रदर्शन है।

जॉन फेयरबैर्न ने 1997 में हास्केल कैफे मेलिंग सूची में एक कार्यात्मक ढेर लगाया।

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

मैं इसे नीचे पुन: पेश करता हूं, इस स्थान को फिट करने के लिए पुन: स्वरूपित किया गया है। मैंने मर्ज_हाइप के कोड को भी थोड़ा सरल किया है।

मुझे आश्चर्य है कि जब से यह इतना उपयोगी है, तो मैं मानक प्रस्तावना में नहीं हूँ। अक्टूबर 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)

यहाँ एक पृष्ठ है जिसमें HeapSort का ML संस्करण है। यह काफी विस्तृत है और एक अच्छी शुरुआत प्रदान करनी चाहिए।

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

आप ST मोनाड का उपयोग भी कर सकते हैं, जो आपको अनिवार्य कोड लिखने की अनुमति देता है, लेकिन एक विशुद्ध रूप से कार्यात्मक इंटरफ़ेस को सुरक्षित रूप से उजागर करता है।

हास्केल में लिखे गए कुशल क्विकसॉर्ट एल्गोरिदम की तरह, आपको सामान रखने के लिए मोनाड्स (राज्य ट्रांसफार्मर) का उपयोग करने की आवश्यकता है।