क्या कुछ ऐसा है (xs: x)

Question

मैं हास्केल के लिए नया हूं। मैं जानता हूँ कि मैं ऐसा करने से एक reverse समारोह बना सकते हैं:

reverse :: [a] -> [a] 
reverse [] = [] 
reverse (x:xs) = (Main.reverse xs) ++ [x] 

वहाँ (xs:x) के रूप में ऐसी बात है (एक तत्व के साथ concatenated एक सूची, यानी x सूची में अंतिम तत्व है) ताकि मैं पिछले डाल सूची के सामने सूची तत्व?

rotate :: [a] -> [a] 
rotate [] = [] 
rotate (xs:x) = [x] ++ xs 

मैं जब मैं इस समारोह युक्त एक कार्यक्रम संकलन करने की कोशिश इन त्रुटियों को मिलता है: अपने बाद के उदाहरण में

Occurs check: cannot construct the infinite type: a = [a] 
When generalising the type(s) for `rotate' 

Answer 1

मैं हास्केल के लिए भी नया हूं, इसलिए मेरा जवाब आधिकारिक नहीं है। वैसे भी, मैं इसे last और init का उपयोग कर करना होगा:

Prelude> last [1..10] : init [1..10] 
[10,1,2,3,4,5,6,7,8,9] 

या

Prelude> [ last [1..10] ] ++ init [1..10] 
[10,1,2,3,4,5,6,7,8,9] 

Answer 2

, x एक सूची वास्तव में है। [x] सूचियों की एक सूची बन जाता है, उदा। [[1,2], [3,4]]।

(++) दोनों तरफ एक ही प्रकार की सूची चाहता है। जब आप इसका उपयोग कर रहे हों, तो आप [[a]] ++ [a] कर रहे हैं, यही कारण है कि संकलक शिकायत कर रहा है। आपके कोड a के अनुसार [a] जैसा ही होगा, जो असंभव है।

(x:xs) में, x सूची (सिर) और xs का पहला आइटम है, लेकिन सिर, यानी पूंछ है। नाम यहां अप्रासंगिक हैं, आप उन्हें (head:tail) पर भी कॉल कर सकते हैं।

rotate :: [a] -> [a] 
rotate [] = [] 
rotate lst = (last lst):(rotate $ init lst) 

N.B.:

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

Answer 3

पीछे के रूप में आप बहुत कम कुशल हो सकता है का सुझाव दिया। आखिरी ओ (1) ऑपरेशन नहीं है, लेकिन ओ (एन) है और इसका मतलब है कि आपके द्वारा सुझाए गए घूर्णन ओ (एन^2) alghorhim बन जाता है।

स्रोत: http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/src/GHC-List.html#last

आपका पहला संस्करण हे (एन) जटिलता है। खैर यह नहीं, क्योंकि ++ भी हे है (एन) आपरेशन

है आप इस तरह

rotate l = rev l [] 
    where 
     rev []  a = a 
     rev (x:xs) a = rev xs (x:a) 

स्रोत करना चाहिए: http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/src/GHC-List.html#reverse

Answer 4

आप सादे से कुछ अलग करने का उपयोग करने को तैयार हैं सूचियां, here दस्तावेज के रूप में, आप Seq कंटेनर पैकेज में टाइप कर सकते हैं। इसमें ओ (1) विपक्ष (सामने वाला तत्व) और स्नोक (पीठ पर तत्व) है, और दृश्यों के उपयोग के माध्यम से, सामने और पीछे से तत्व मिलान करने वाले पैटर्न की अनुमति देता है।

Answer 5

"क्या ऐसी कोई चीज है (xs: x) (किसी तत्व के साथ सम्मिलित एक सूची, यानी x सूची में अंतिम तत्व है) ताकि मैं सूची के सामने अंतिम सूची तत्व डालूं?"

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

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

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

एक डेटा संरचना अवधारणा के कई कार्यान्वयन के बारे में सोचना बिल्कुल उचित है - थोड़ी देर के लिए, यह हास्केल की कक्षा/आवृत्ति परिभाषाओं का एक उपयोग है।

Answer 6

संक्षिप्त उत्तर यह है: पैटर्न मिलान के साथ यह संभव नहीं है, आपको एक फ़ंक्शन का उपयोग करना होगा।

लंबा उत्तर यह है: यह मानक हास्केल में नहीं है, लेकिन यदि आप व्यू पैटर्न नामक एक एक्सटेंशन का उपयोग करने के इच्छुक हैं, और यदि आपको अपने पैटर्न मिलान में कोई समस्या नहीं है तो अंततः निरंतर समय से अधिक समय लेना।

कारण यह है कि पैटर्न मिलान पहली जगह संरचना का निर्माण कैसे किया जाता है इस पर आधारित है।

data List a = Empty | Cons a (List a) 
      deriving (Show) -- this is just so you can print the List 

आप की तरह है कि आप तीन वस्तुओं उत्पन्न एक प्रकार की घोषणा जब: एक प्रकार निर्माता List, और दो डेटा कंस्ट्रक्टर्स: Empty और Cons सूची एक सार प्रकार है, जो निम्नलिखित संरचना है। प्रकार का कन्स्ट्रक्टर प्रकार लेता है और उन्हें अन्य प्रकारों में बदल देता है, यानी List एक प्रकार a लेता है और एक और प्रकार List a बनाता है। डेटा कन्स्ट्रक्टर एक ऐसे फ़ंक्शन की तरह काम करता है जो List a प्रकार का कुछ देता है। इस मामले में आप हैं:

Empty :: List a 

एक खाली सूची और

Cons :: a -> List a -> List a 

किस प्रकार a और एक सूची के एक मूल्य लेता है और सूची के सिर के लिए मूल्य जोड़ देती है, एक और सूची लौटने का प्रतिनिधित्व। तो अगर आप इस तरह अपनी सूची का निर्माण कर सकते हैं:

empty = Empty   -- similar to [] 
list1 = Cons 1 Empty -- similar to 1:[] = [1] 
list2 = Cons 2 list1 -- similar to 2:(1:[]) = 2:[1] = [2,1] 

यह कम या ज्यादा कैसे सूचियों के काम है, लेकिन Empty के स्थान पर आप [] है और Cons के स्थान पर आप (:) है।जब आप [1,2,3] जैसे कुछ टाइप करते हैं तो यह 1:2:3:[] या Cons 1 (Cons 2 (Cons 3 Empty)) के लिए सिंटैक्टिक चीनी है।

जब आप पैटर्न मिलान करते हैं, तो आप इस प्रकार को "डी-कंस्ट्रक्शन" कर रहे हैं। किस प्रकार संरचित किया गया है, इस बारे में ज्ञान रखने से आप इसे विशिष्ट रूप से अलग कर सकते हैं। फ़ंक्शन पर विचार करें:

head :: List a -> a 
head (Empty) = error " the empty list have no head" 
head (Cons x xs) = x 

टाइप मिलान पर क्या होता है यह है कि डेटा कन्स्ट्रक्टर आपके द्वारा दी गई कुछ संरचनाओं से मेल खाता है। यदि आपके पास खाली सूची होने की तुलना में Empty से मेल खाता है। यदि मेल खाता है Const x xs तो x प्रकार a होना आवश्यक है और सूची के सिर होना चाहिए और xs प्रकार List a है और सूची की पूंछ होना चाहिए, कि डेटा निर्माता के प्रकार है कारण:

Cons :: a -> List a -> List a 

हैं Cons x xsx से List a प्रकार a और xsList a होना चाहिए। वही सच है (x: xs)। आप GHCi में की (:) प्रकार के लिए तत्पर हैं:

> :t (:) 
(:) :: a -> [a] -> [a] 

तो, अगर (एक्स: XS) प्रकार [a] की है, xa होना चाहिए और xs[a] होना चाहिए। जब आप (xs:x) करने का प्रयास करते हैं तो त्रुटि संदेश मिलता है और फिर xs किसी सूची की तरह व्यवहार करता है, ठीक इसी कारण है। (:) के उपयोग से कंपाइलर अनुमान लगाता है कि xs टाइप a है, और के उपयोग से, यह अनुमान लगाता है कि xs[a] होना चाहिए। फिर यह बाहर निकलता है क्योंकि कोई सीमित प्रकार a नहीं है जिसके लिए a = [a] - यही वह है जो वह आपको उस त्रुटि संदेश के बारे में बताने की कोशिश कर रहा है।

यदि आपको अन्य तरीकों से संरचना को अलग करने की आवश्यकता है जो डेटा कन्स्ट्रक्टर संरचना के निर्माण के तरीके से मेल नहीं खाता है, तो आपको अपना स्वयं का फ़ंक्शन लिखना होगा। मानक लाइब्रेरी में दो कार्य हैं जो आप चाहते हैं: last किसी सूची का अंतिम तत्व देता है, और init सूची के सभी-अंतिम-अंतिम तत्व लौटाता है।

लेकिन ध्यान दें कि पैटर्न मिलान निरंतर समय में होता है। सूची और सूची की पूंछ का पता लगाने के लिए, इससे कोई फ़र्क नहीं पड़ता कि सूची कितनी देर तक है, आपको केवल बाहरी डेटा कन्स्ट्रक्टर को देखना होगा। अंतिम तत्व ढूंढना O(N) है: जब तक आपको सबसे कम Cons या सबसे कम (:) नहीं मिल जाता है, तब तक आपको खुदाई करनी होगी, और इसके लिए आपको एन बार संरचना "छील" की आवश्यकता होती है, जहां एन सूची का आकार है।

यदि आपको अक्सर लंबी सूचियों में अंतिम तत्व देखना है, तो आप शायद इस बात पर विचार कर सकते हैं कि सूची का उपयोग करना एक अच्छा विचार है। (पहले और अंतिम तत्वों तक निरंतर समय तक पहुंच), Data.Map (log(N) यदि आप इसकी कुंजी जानते हैं तो किसी भी तत्व के लिए समय पहुंच), Data.Array (यदि आप इसकी अनुक्रमणिका जानते हैं तो तत्व के निरंतर समय तक पहुंच) Data.Vector या अन्य डेटा संरचनाओं की तुलना में आपकी आवश्यकताओं से मेल खाने वाली संरचनाएं।

ठीक है। वह छोटा जवाब था (: पी)। लंबे समय तक आपको खुद को थोड़ा सा देखना होगा, लेकिन यहां एक परिचय है।

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

{-# Language ViewPatterns #-} 

कि यह कैसे उपयोग करने के लिए के निर्देश यहां हैं: http://hackage.haskell.org/trac/ghc/wiki/ViewPatterns

आप की तरह कुछ कर सकता है दृश्य पैटर्न के साथ

: x

view :: [a] -> (a, [a]) 
view xs = (last xs, init xs) 

someFunction :: [a] -> ... 
someFunction (view -> (x,xs)) = ... 

से और xslast और सूची आप someFunction करने के लिए प्रदान की init के लिए बाध्य होंगे। संवैधानिक रूप से यह पैटर्न मिलान की तरह लगता है, लेकिन यह वास्तव में दिए गए सूची में last और init लागू कर रहा है।