एक शुद्ध रूप से कार्यात्मक प्रोग्रामिंग भाषा में संदेह से जुड़ी सूची

Question

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

Answer 1

एक शुद्ध कार्यात्मक भाषा में, एक दोगुनी-लिंक्ड सूची दिलचस्प नहीं है। एक दोगुनी लिंक्ड सूची का विचार एक नोड को पकड़ने और किसी भी दिशा में जाने, या सूची के बीच में विभाजित करने में सक्षम होना है।

• एक बीच में एक सूचक, जिसमें से आप बायें या दायें (एक के संस्करण जा सकते हैं साथ अकेले लिंक्ड सूची Huet की: एक शुद्ध functionaly भाषा में आप शायद इन दो डेटा संरचनाओं में से एक के साथ बेहतर कर रहे हैं "जिपर")

• एक उंगली का पेड़, जो राल्फ हिनज और रॉस पैटरसन द्वारा आविष्कार किया गया एक मस्तिष्क-उड़ाने वाली डेटा संरचना है।

मैं जिपर का एक बड़ा प्रशंसक हूं; यह कई स्थितियों में उपयोगी है।

Answer 2

कई दृष्टिकोण हैं।

यदि आप इसे बनाने के बाद दोगुनी-लिंक्ड सूची को उत्परिवर्तित नहीं करना चाहते हैं तो आप आलस्य पर भरोसा करके 'गाँठ बांध सकते हैं'।

http://hackage.haskell.org/packages/archive/liboleg/2009.9.1/doc/html/Data-FDList.html

: एक ला चाल ओलेग Kiseylov द्वारा प्रस्तावित और यहां लागू किया -

http://www.haskell.org/haskellwiki/Tying_the_Knot

आप एक परिवर्तनशील दोगुना से जुड़े सूची चाहते हैं तो आप नकली संदर्भों को किसी भी तरह की जरूरत है - या का उपयोग असली

दिलचस्प बात यह है कि पूर्व मूल रूप से सफल होने के लिए आलस्य पर निर्भर करता है। आपको अंततः गाँठ बांधने के लिए उत्परिवर्तन या आलस्य की आवश्यकता होती है।

Answer 3

मैं संगीतफ़ान के प्रश्न को दोहराता हूं: "आपको इसके लिए वास्तव में क्या चाहिए?" जैसा कि नॉर्मन रैमसे ने नोट किया: यदि आपको बहु-दिशात्मक ट्रैवर्सल की आवश्यकता है, तो ज़िप्पर आसान हैं; यदि आपको तेजी से विभाजन की आवश्यकता है, तो उंगली के पेड़ अच्छी तरह से काम करते हैं।

लेकिन, सिर्फ यह कैसे लग रहा है देखने के लिए ...

import Control.Arrow 
import Data.List 

data LNode a = LNode { here :: a, prev :: LList a, next :: LList a } 
type LList a = Maybe (LNode a) 

toList :: LList a -> [a] 
toList = unfoldr $ fmap $ here &&& next 

fromList :: [a] -> LList a 
fromList l = head nodes where 
    nodes = scanr ((.) Just . uncurry LNode) Nothing $ zip l $ Nothing : nodes 

append :: LList a -> LList a -> LList a 
append = join Nothing where 
    join k (Just a) b = a' where 
     a' = Just $ a { prev = k, next = join a' (next a) b } 
    join k _ (Just b) = b' where 
     b' = Just $ b { prev = k, next = join b' Nothing (next b) } 
    join _ _ _ = Nothing 

Answer 4

OCaml में, परिपत्र के लिए बस लिंक्ड सूची आप हमेशा ऐसा ही कुछ कर सकते हैं:

type t = { a : t Lazy.t } 

let cycle n = 
    let rec start = {a = lazy (aux n) } 
    and aux = function 
    | 0 -> start 
    | n -> { a = lazy (aux (n-1))} 
    in start 

दोगुना जुड़ा हुआ सूचियों के लिए, मुझे कल्पना है कि ऐसा कुछ करना संभव है। लेकिन आपको टाइपिंग की बात आती है जब आपको आलस्य पर भरोसा करना पड़ता है और अभिलेखों पर अनुकूल संरचनाएं होती हैं। त्वरित और गंदे चक्रीय दोगुनी जुड़ी सूची:

type 'a t = { data : 'a; before : 'a t Lazy.t; after : 'a t Lazy.t } 

    let of_list l = 
    match l with [] -> assert false | hd::tl -> 
    let rec start = { data = hd; before = last; after = next } 
    and couple = lazy (aux (lazy start) hd) 
    and next = lazy (Lazy.force (fst (Lazy.force couple))) 
    and last = lazy (Lazy.force (snd (Lazy.force couple))) 
    and aux before = function 
    | [] -> (lazy start), before 
    | hd::tl -> let rec current = lazy { data = hd; before = before; after = after } 
        and couple = lazy (aux current tl) 
        and after = lazy (Lazy.force (fst (Lazy.force couple))) 
        and last = lazy (Lazy.force (snd (Lazy.force couple))) in 
        current, last 
    in start