द्वि-आयामी जिपर

Question

हास्केल में 2 डी ग्रिड के बारे में हालिया प्रश्न से प्रेरित, मुझे आश्चर्य है कि सूचियों की सूची में स्थिति का ट्रैक रखने के लिए दो-आयामी जिपर बनाना संभव होगा। एक सूची में एक आयामी जिपर हमें वास्तव में बड़ी सूची में स्थानीय स्तर पर कुशलता से स्थानांतरित करने की अनुमति देता है (सामान्य पाठ पाठ संपादक होने का)। लेकिन कहते हैं कि हम इस तरह की सुविधा देता है एक दूसरे आयाम है:

grid = 
    [[ 1, 2, 3, 4, 5] 
    ,[ 6, 7, 8, 9,10] 
    ,[11,12,13,14,15] 
    ,[16,17,18,19,20] 
    ,[21,22,23,24,25]] 

हम ज़िपर डेटा संरचना के कुछ प्रकार बना सकते हैं कुशलतापूर्वक न केवल छोड़ दिया और सही, लेकिन ऊपर और ग्रिड यहाँ में नीचे ले जाने के लिए? यदि हां, तो क्या होगा यदि हम सूचियों की सूची को अनंत सूचियों की अनंत सूची के साथ प्रतिस्थापित करते हैं, तो क्या हम अभी भी कुशल आंदोलन प्राप्त कर सकते हैं?

Answer 1

काफी, नहीं। ज़िप्पर कैसे काम करते हैं, इसके प्रमुख पहलुओं में से एक यह है कि वे उस तक पहुंचने के लिए उपयोग किए जाने वाले पथ से संरचना में एक स्थान का प्रतिनिधित्व करते हैं, साथ ही रास्ते में बनाए गए अतिरिक्त टुकड़े, अंत परिणाम के साथ कि आप उस पथ के साथ पीछे हट सकते हैं और संरचना को पुनर्निर्माण कर सकते हैं तुम जाओ। डेटा संरचना के माध्यम से उपलब्ध पथों की प्रकृति इस प्रकार जिपर को बाधित करती है।

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

2 डी स्पेस में मनमाने ढंग से आंदोलन वास्तव में उपरोक्त आवश्यकताओं को फिट नहीं करता है, इसलिए हम यह समझ सकते हैं कि 2 डी जिपर कुछ हद तक सीमित होगा। शायद आप मूल से शुरू करेंगे, संरचना के माध्यम से एक मार्ग चलेंगे, और फिर उस बिंदु के साथ अन्य बिंदुओं तक पहुंचने के लिए उस दूरी के साथ कुछ दूरी पीछे हटें। यह भी दर्शाता है कि संरचना में किसी भी बिंदु के लिए, अन्य बिंदु भी हैं जिन्हें मूल के माध्यम से ही पहुंचा जा सकता है।

क्या आप कर सकते हैं डेटा संरचना में 2 डी दूरी की कुछ धारणा बनाते हैं, ताकि आप संरचना के माध्यम से पथ का अनुसरण कर सकें, "नीचे" अंक एक-दूसरे के करीब हैं; विचार 2 डी स्पेस में थोड़ी दूरी को स्थानांतरित करने के लिए औसत पर आवश्यक बैकट्रैकिंग की मात्रा को कम करना है। यह लगभग खोज 2 डी स्पेस तक दूरी के साथ लगभग उसी दृष्टिकोण के रूप में समाप्त होता है - निकटतम पड़ोसी खोज, कुशल ज्यामितीय चौराहे, उस तरह की चीज - और उसी प्रकार की डेटा संरचना, अर्थात् space partitioning के साथ किया जा सकता है उच्च आयामी खोज पेड़। quadtree, kd-tree के लिए एक जिपर कार्यान्वित करना, या इसी तरह की संरचनाएं किसी भी अन्य पेड़ की तरह सीधी है।

Answer 2

ठीक है आप निम्न कोड की तरह कुछ सरल उपयोग कर सकते हैं। हम चयनित तत्व की शीर्ष पंक्तियों, चयनित तत्व की निचली पंक्तियों, साथ ही चयनित व्यक्ति के बाईं ओर वाले तत्वों और चयनित व्यक्ति के दाईं ओर वाले तत्वों द्वारा एक तालिका का प्रतिनिधित्व करते हैं।

शीर्ष पंक्तियों और बाएं तत्व कुशल आंदोलन को सक्षम करने के लिए एक विपरीत क्रम में संग्रहीत किए जाते हैं।

मुझे यकीन नहीं है कि यह एक जिपर के रूप में योग्य है, हालांकि, हालांकि हम डेटा संरचना में "स्थान" रखते हैं, यह "पथ" नहीं है।

-- Table sel left right top bottom 
data Table a = Table a [a] [a] [[a]] [[a]] deriving Show 

left :: Table a -> Table a 
left tab@(Table _ [] _ _ _) = tab 
left (Table sel (l:ls) rs ts bs) = Table l ls (sel:rs) ts bs 

right :: Table a -> Table a 
right tab@(Table _ _ [] _ _) = tab 
right (Table sel ls (r:rs) ts bs) = Table r (sel:ls) rs ts bs 

up :: Table a -> Table a 
up tab@(Table _ _ _ [] _) = tab 
up (Table sel ls rs (t:ts) bs) = Table sel' ls' rs' ts (b:bs) 
    where 
    (ls',(sel':rs')) = splitAt (length ls) t 
    b = ls ++ (sel:rs) 

down :: Table a -> Table a 
down tab@(Table _ _ _ _ []) = tab 
down (Table sel ls rs ts (b:bs)) = Table sel' ls' rs' (t:ts) bs 
    where 
    (ls',(sel':rs')) = splitAt (length ls) b 
    t = ls ++ (sel:rs) 

tableToList :: Table a -> [[a]] 
tableToList (Table sel ls rs ts bs) = (reverse ts) ++ [ls ++ (sel:rs)] ++ bs 

listToTable :: [[a]] -> Table a 
listToTable [] = error "cannot make empty table" 
listToTable ([]:_) = error "cannot make empty table" 
listToTable ((t:tr):ts) = Table t [] tr [] ts 

यह भी अनंत सूचियों के लिए काम करता है -

selected :: Table a -> a 
selected (Table sel _ _ _ _) = sel 

a :: Table Int 
a = listToTable $ replicate 10 [1..] 

selected a     #=> 1 
selected $ down a   #=> 1 
selected $ right $ down a #=> 2