हास्केल में सूचीबद्ध: डेटा प्रकार या सार डेटा प्रकार?

Question

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

फिर सूची प्रकार को हास्केल में कैसे योग्य किया जा सकता है? क्या यह एक "डेटा प्रकार" या "अमूर्त डेटा प्रकार" है? और कार्यान्वित की लिंक्ड सूची प्रकार का क्या?

इसके अतिरिक्त, चूंकि प्रीलूड द्वारा प्रदान की गई सूची प्रकार एक लिंक्ड सूची प्रकार नहीं है, मूलभूत लिंक सूची कैसे लागू की जा सकती है?

उदाहरण के लिए, एक सूची के सूचकांक n पर एक तत्व एक जोड़ने के लिए डिज़ाइन कोड के इस टुकड़े:

add [] acc _ _ = reverse acc 
add (x:xs) acc 0 a = add xs (x:a:acc) (-1) a 
add (x:xs) acc n a = add xs (x:acc) (n-1) a 

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

कृपया, अगर मैंने जो भी कहा है, उसे सही करने में संकोच न करें, और आपके समय के लिए धन्यवाद।

Answer 1

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

आपको लगता है कि समारोह सबसे बस इस तरह से निर्धारित कर सकते हैं:

add ls idx el = take idx ls ++ el : drop idx ls 

सूची el : drop idx ls मूल सूची की पूंछ पुनः उपयोग कर लेता है, तो आप केवल idx को एक नई सूची उत्पन्न करने के लिए है (जो क्या take समारोह करता है)। आप स्पष्ट प्रत्यावर्तन का उपयोग कर इसे क्या करना चाहते हैं, तो आप यह इतना की तरह निर्धारित कर सकते हैं:

add ls 0 el = el : ls 
add (x:xs) idx el 
    | idx < 0 = error "Negative index for add" 
    | otherwise = x : add xs (idx - 1) el 
add [] _ el = [el] 

यह उसी तरह से सूची की पूंछ (कि पहले मामले में el : ls है) पुनः उपयोग कर लेता।

चूंकि आपको यह देखने में परेशानी हो रही है कि यह एक लिंक्ड सूची कैसे है, आइए देखें कि एक लिंक की गई सूची क्या है: यह एक डेटा संरचना है जिसमें कोशिकाएं होती हैं, जहां प्रत्येक सेल का मूल्य होता है और अगले आइटम का संदर्भ होता है ।

struct ListCell { 
void *value; /* This is the head */ 
struct ListCell *next; /* This is the tail */ 
} 

लिस्प में, यह (head . tail), जहां head मूल्य है और tail अगले आइटम पर संदर्भ के रूप में परिभाषित किया है: सी में, यह के रूप में परिभाषित किया जा सकता है।

हास्केल में, इसे data [] a = [] | a : [a] के रूप में परिभाषित किया गया है, जहां a मान है और [a] अगले आइटम का संदर्भ है।

जैसा कि आप देख सकते हैं, ये डेटा संरचनाएं समकक्ष हैं। केवल अंतर यह है कि सी और लिस्प में, जो पूरी तरह कार्यात्मक नहीं हैं, सिर और पूंछ मूल्य वे चीजें हैं जिन्हें आप बदल सकते हैं। हास्केल में, आप उन्हें बदल नहीं सकते हैं।

Answer 2

हास्केल पूरी तरह कार्यात्मक प्रोग्रामिंग भाषा है। इसका मतलब है कि कोई भी बदलाव नहीं किया जा सकता है।

सूचियां गैर-सार प्रकार हैं, यह सिर्फ एक लिंक की गई सूची है।

आप उन्हें इस तरह से परिभाषित किया गया के बारे में सोच सकते हैं:

data [a] = a : [a] | [] 

जो ठीक वैसी ही एक लिंक्ड सूची परिभाषित किया जाता है - एक सिर तत्व और (एक सूचक) बाकी।

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

Answer 3

आपका कोड काम कर सकता है, लेकिन यह निश्चित रूप से अनुकूल नहीं है। मामले लो जहाँ आप एक उदाहरण सूचकांक 0. पर एक आइटम सम्मिलित करना चाहते हैं: आप इस के लिए व्युत्पत्ति का पालन करें

add [200, 300, 400] [] 0 100 

, आप के साथ अंत:

add [200, 300, 400] [] 0 100 
add [300, 400] (200:100:[]) (-1) 100 
add [400] (300:[200, 100]) (-2) 300 
add [] (400:[300, 200, 100]) (-3) 400 
reverse [400, 300, 200, 100] 
[100, 200, 300, 400] 

लेकिन हम केवल एक जोड़ रहे हैं सूची की शुरुआत में आइटम! ऐसा ऑपरेशन सरल है! यह है (:)

add [200, 300, 400] [] 0 100 
100:[200, 300, 400] 
[100, 200, 300, 400] 

इस बारे में सोचें कि सूची में से कितनी चीजों को वास्तव में उलटना आवश्यक है।

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

Answer 4

पुन: एक सूची के अंत में कोई तत्व जोड़, मैं (++) ऑपरेटर और splitAt समारोह उपयोग करने का सुझाव चाहते हैं:

add xs a n = beg ++ (a : end) 
    where 
    (beg, end) = splitAt n xs 

List किसी लिंक किए गए सूची है, लेकिन यह केवल पढ़ने के लिए है। आप List को जगह में संशोधित नहीं कर सकते - इसके बजाय आप एक नया List संरचना बना सकते हैं जिसमें आपके इच्छित तत्व हैं। मैंने इसे पढ़ा नहीं है, लेकिन this book शायद आपके अंतर्निहित प्रश्न पर आता है।

HTH

Answer 5

हास्केल में, "डेटा प्रकार" और "सार प्रकार" कला की दृष्टि से कर रहे हैं:

• ए 'डेटा प्रकार "(जो सार नहीं है) दिखाई मूल्य कंस्ट्रक्टर्स है आप जो case अभिव्यक्तियों या फ़ंक्शन परिभाषाओं में पैटर्न-मिलान कर सकते हैं।

• एक "सार प्रकार" में दृश्यमान मूल्य निर्माता नहीं हैं, इसलिए आप प्रकार के मानों पर पैटर्न मिलान नहीं कर सकते हैं।

एक प्रकार a, [a] (a की सूची) एक डेटा प्रकार है क्योंकि आप कर सकते हैं दिखाई कंस्ट्रक्टर्स विपक्ष पर पैटर्न मैच (लिखित :) और शून्य (लिखित []) है को देखते हुए। एक अमूर्त प्रकार का एक उदाहरण IO a होगा, जिसे आप पैटर्न मिलान द्वारा deconstruct नहीं कर सकते हैं।

Answer 6

कंपाइलर किसी भी सूची के लिए इच्छित आंतरिक प्रतिनिधित्व चुनने के लिए स्वतंत्र है। और व्यवहार में यह वास्तव में भिन्न होता है। स्पष्ट रूप से सूची "[1 ..]" को विपक्षी कोशिकाओं की शास्त्रीय श्रृंखला के रूप में लागू नहीं किया गया है।

वास्तव में एक आलसी सूची एक थंक के रूप में संग्रहीत की जाती है जो अगले मूल्य और अगले थंक वाले एक विपक्षी सेल का मूल्यांकन करती है (एक थंक मूल रूप से एक फ़ंक्शन पॉइंटर और फ़ंक्शन के लिए तर्क है, जो वास्तविक मूल्य से प्रतिस्थापित हो जाता है एक बार समारोह कहा जाता है)। दूसरी ओर यदि संकलक में सख्तता विश्लेषक साबित कर सकता है कि पूरी सूची का हमेशा मूल्यांकन किया जाएगा तो संकलक केवल पूरी सूची को विपक्षी कोशिकाओं की श्रृंखला के रूप में बना देगा।