हास्केल: कुंजी

Question

द्वारा समूहित (ए, [बी]) की सूची में (ए, बी) कुंजी-मूल्य जोड़े (संभावित रूप से दोहराए गए कुंजियों के साथ) की सूची को परिवर्तित करना, मैं एक हास्केल शुरुआती हूं। मान लीजिए कि मैं एक फ़ंक्शन convertKVList लिखना चाहता हूं जो कि कुंजी-मान जोड़े की एक विस्तृत सूची लेता है, जहां कुछ कुंजियों को दोहराया जा सकता है, और इसे कुंजी से सूचियों की सूची में मैपिंग में बदल देता है जहां सभी चाबियाँ अद्वितीय होती हैं। उदाहरण के लिए, Int के जोड़ों की सूची पर, मैं इस व्यवहार को चाहते हैं:

> convertKVList [(1, 2), (1, 4), (1, 3), (2, 3)] 
[(1,[3,4,2]),(2,[3])] 

यह एक आम पर्याप्त काम की तरह लगता है कि वहाँ एक पुस्तकालय है कि मैं क्या करना चाहते हैं के लिए उपलब्ध समारोह होना चाहिए, लेकिन मैं नहीं कर सके ' जब मैंने देखा तो कुछ भी नहीं मिला। अंत में, किसी ने सुझाव दिया कि मैं Map.fromListWith (++) साथ Map.toList रचना, और मैं इस के साथ समाप्त हो गया:

import Data.Map as Map (toList, fromListWith) 

convertKVList :: (Ord a) => [(a, b)] -> [(a, [b])] 
convertKVList ls = 
    (Map.toList . Map.fromListWith (++) . map (\(x,y) -> (x,[y]))) ls 

मेरा प्रश्न अधिक अनुभवी Haskellers के लिए है और दो भागों में है: सबसे पहले, यह कैसे आप इसके बारे में जाना होगा, या क्या कोई "बेहतर" (पढ़ने में आसान, या अधिक कुशल, या दोनों) तरीका है?

दूसरा, मैं अपने साथ इस तरह कैसे आ सकता हूं? मुझे पता था कि मैं चाहता था कि यह प्रकार [(a, b)] -> [(a, [b])] हो, लेकिन होउगल में डालने से कुछ भी उपयोगी नहीं हुआ। और मैंने Data.Map दस्तावेज़ों को देखा था, लेकिन न तो fromListWith और न ही toList विशेष रूप से सहायक के रूप में बाहर निकल गया था। तो: आप इस समस्या के बारे में सोचने के बारे में कैसे जाएंगे? (मुझे एहसास है कि ये दोनों प्रश्न व्यक्तिपरक हैं, खासकर दूसरा।)

धन्यवाद!

Answer 1

फ़ंक्शन लिखते समय सबसे महत्वपूर्ण बिंदुओं में से एक, अलग-अलग उप-कार्यों (जो अंत में फ़ंक्शन संरचना द्वारा अक्सर एक साथ रखा जाता है) में विभाजित करने की कोशिश कर रहा है। जिससे

1. एक सिंगलटन सूची में प्रत्येक जोड़ी के 2 घटक के नक्शे (: उदाहरण के लिए, परिभाषा में आप के साथ, वहाँ तीन कार्यों (आवेदन के क्रम में, सही परिभाषा से बाईं ओर यानी) कर रहे हैं आया (जो एक सूची में बराबर कुंजी के साथ प्रविष्टियों)
2. यह मोड़ विलय

मैं एक अलग समाधान (जो एक सटीक प्रतिलिपि था पोस्ट करने के लिए करना चाहता था का ख्याल रखता है Map.fromListWith का उपयोग)

कोई मानचित्र बनाने को सक्षम करने कोड मार्क के बीच में पोस्ट किया गया;))। बस यह स्पष्ट करने के लिए कि अधिकांश समय एक ही लक्ष्य के लिए अलग-अलग मार्ग हैं।

1. तरह कुंजियों से सूची
2. समूह कुंजी द्वारा परिणाम
3. यह मोड़ इच्छित प्रकार की एक सूची में

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

Answer 2

इस जबकि कोई विहित तरह से है:

import Data.List 
import Data.Ord 
import Data.Function (on) 

convertKVList :: Ord a => [(a,b)] -> [(a,[b])] 
convertKVList = map (\x -> (fst $ head x, map snd x)) . groupBy ((==) `on` fst) . sortBy (comparing fst) 

यह Data.Map में खींच नहीं का लाभ है। असम्बद्ध रूप से वही होना चाहिए, बेंचमार्क नहीं किया है। मुझे लगता है कि आप नियंत्रण के साथ पहले खंड को साफ कर सकते हैं। एरो (कुछ ऐसा (fst। Head & & & मानचित्र एसएनडी)) लेकिन यह स्पष्ट रूप से क्लीनर नहीं है।

यह सुनिश्चित नहीं है कि आप इसे कैसे जानते हैं या इसे # हास्केल में पूछकर छोड़कर इसे कैसे करेंगे।

Answer 3

तो, मेरा समाधान पैटर्न मिलान से अधिक है क्योंकि मुझे वास्तव में नहीं पता कि मानक पुस्तकालय में कौन से फ़ंक्शन हैं।

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

और यदि मूल सूची क्रमबद्ध नहीं है, तो sortBy है।

import Data.List 
import Data.Ord 

ls = [(2, 1), (1, 2), (1, 4), (1, 3), (2, 3)] 

addval [] (k, v)= [(k, [v])] 
addval ((k1, vals) : xs) (k2, v) | k1 == k2 
    = ((k1, (v : vals)) : xs) 
addval ls (k, v) = ((k, [v]) : ls) 

convert ls = foldl addval [] (sortBy (comparing fst) ls) 

बदसूरत कोड, लेकिन यह मानचित्र का उपयोग करने से बचाता है।

Answer 4

होगल एकमात्र खोज इंजन नहीं है जो हास्केल पुस्तकालयों को टाइप हस्ताक्षर द्वारा खोजने में सक्षम है और यह निश्चित रूप से और दुर्भाग्य से हैकेज के केवल एक छोटे हिस्से को कवर करता है। एक प्रकार हस्ताक्षर [(a,b)]->[(a,[b])] के लिए Hayoo साथ सर्च कर रहे हैं इन दो कार्यान्वयन लाया:

• aggregateAL
• alistCollect

समस्या पर अपने ले के संबंध में, के बाद से अपने कार्य में आप पहले से ही एक उच्च स्तर आंकड़ा संरचना को लाने (Map), आउटपुट में एक अधिक आदिम सहयोगी सूची में डाउनग्रेड करने का अर्थ नहीं है, क्योंकि:

1. अधिकांश एल्गोरिदम आप संभवतः ऐसे डेटा का उपयोग कर सकते हैं, केवल Map इनपुट प्राप्त करने से लाभ होगा, क्योंकि यह कुंजी-मूल्य स्टोर से निपटने के लिए अधिक प्रभावी है, और यदि आपको कभी भी एक सूची की आवश्यकता होती है तो आप हमेशा उपयोग कर सकते हैं जगह में toList।
2. Map टाइप स्तर पर डुप्लिकेट कुंजी की अनुपस्थिति का तात्पर्य है, जो कि कोई भी कम महत्वपूर्ण नहीं है, क्योंकि हास्केल में आपको हमेशा टाइप-सिस्टम का उपयोग करके अधिकतम सबूत करना चाहिए। यह सिद्धांत अनिवार्य रूप से कथन बनाता है "यदि यह संकलित करता है, तो यह" सत्य के निकटतम "काम करता है।

   convertKVList :: (Ord a) => [(a, b)] -> Map a [b] 
   convertKVList ls = 
       Map.fromListWith (++) . map (\(x,y) -> (x,[y])) $ ls 
   

   Hayooing उस प्रकार हस्ताक्षर के लिए पहले से ही लागू किया परिणामों के एक जोड़े को भी लाता है:

दूसरे शब्दों में यह अपने कार्य की सही परिभाषा है।

समस्या के करीब आने के बारे में, यह क्लासिक है: "Divide and conquer!"। क्रिस के जवाब में कुछ अच्छे अंक भी हैं।

Answer 5

एक समझ में आता समाधान की तरह लग रहा है कि और आप इसे साफ कर सकते हैं थोड़ा और अधिक:

 
import Data.Map (toList, fromListWith) 
import Control.Arrow (second) 

convertKVList :: Ord a => [(a, b)] -> [(a, [b])] 
convertKVList = toList . fromListWith (++) . map (second (:[])) 

कैसे आप अपने दम पर इस के साथ आ सकता है के बारे में: यह सोचते हैं आप Data.Map साथ शुरू किया था, तो आप उपयोग करना चाहते हैं समान कुंजी के साथ मूल्यों को गठबंधन करने के लिए मानचित्र। हैकेज पर Data.Map के लिए प्रलेखन a कुंजी के लिए प्रकार और k कुंजी के लिए है।

यह जानकर, आप a -> a -> a को Map k a में दो मानों को जोड़कर a मान बनाने के लिए खोज सकते हैं। यह एपीआई को insertWith, fromListWith, और fromAscListWith जैसे कुछ हद तक कार्यों को संक्षिप्त करता है।

इसी तरह, अपने Map k a[(k, a)] में बदलने के लिए, आप Map k a -> [(k, a)] के लिए दस्तावेज़ खोज और की तरह assocs, toList, toAscList, और toDescList केवल कुछ कार्यों पा सकते हैं। ध्यान दें कि आपके मामले में, [(k, a)][(Int, [Int])] पर तत्काल है।

मानक हास्केल पुस्तकालयों को समझने में मुझे एक चीज़ मिल गई है जो हैकेज पर स्रोत को देखना है। यह देखते हुए कि दूसरों के संदर्भ में कौन से फ़ंक्शंस लागू किए गए हैं, एपीआई को छोटा महसूस करने में मदद करता है, और मैं देख सकता हूं कि कौन से फ़ंक्शन मूल बिल्डिंग ब्लॉक हैं।

Answer 6

मुझे संदेह है कि उत्परिवर्तन और ST मोनैड में डुबकी के बिना, आपको Map.fromListWith समाधान (या HashMap.fromListWith का उपयोग करने जैसे काफी समकक्ष विकल्प) में सुधार करने की संभावना नहीं है। मैं बस उसके साथ जाऊंगा।

मूल रूप से, उत्परिवर्तन के साथ आप a के साथ एक म्यूटेबल हैश तालिका का उपयोग करके b की कुंजी और परिवर्तनीय सूचियों के रूप में मूल्यों के रूप में इस समूह को निकट-रैखिक समय में कर सकते हैं। उत्परिवर्तन के बिना, हालांकि, यह बदतर होने जा रहा है, क्योंकि एक संतुलित खोज पेड़ में प्रत्येक डालने ओ है (लॉग एन); ऐसा इसलिए है क्योंकि "डालने" का मतलब है कि प्रत्येक पेड़ नोड की एक नई प्रतिलिपि बनाना जो आपके डाले गए तत्व को जाता है। और आपको एन सम्मिलित करने की आवश्यकता होती है - जो आपको ओ (एन * लॉग एन) सीमाएं देता है जो Map.fromListWith समारोह है समय से पहले एसोसिएशन सूची को सॉर्ट करना मूल रूप से इसे बेहतर नहीं करता है, क्योंकि सॉर्टिंग भी ओ (एन * लॉग एन) है।

तो ओ (एन * लॉग एन) में सुधार करने के लिए, आपको उत्परिवर्तन के साथ डेटा संरचनाओं की आवश्यकता है। मैंने अभी एक त्वरित Google किया है और सर्वोत्तम शर्त hashtables लाइब्रेरी (जिसे मैंने कभी कोशिश नहीं की है, तो मैं इसका उपयोग नहीं कर सकता) का उपयोग कर मानक अनिवार्य एल्गोरिदम लागू करना होगा। इसका उपयोग करने के लिए आपको Control.Monad.ST और Data.STRef समझने की आवश्यकता होगी। ST मोनैड एक ऐसी तकनीक है जो जीएचसी एक शुद्ध कार्य में "आंतरिक रूप से" उत्परिवर्तन का उपयोग करने के लिए प्रदान करती है-यह गारंटी देने के लिए कुछ प्रकार के सिस्टम एक्सटेंशन का उपयोग करती है ताकि साइड इफेक्ट्स को प्रश्नों के बाहर नहीं देखा जा सके। HaskellWiki has some examples, लेकिन यह कुछ अध्ययन कर सकता है और इस के साथ सहज महसूस करने के लिए अभ्यास कर सकता है।

दूसरी बात मैं सिफारिश करेंगे, अगर आपको लगता है जैसे आप बेहतर Data.Map या इसी तरह के पुस्तकालयों को समझना चाहते हैं, क्रिस ओकासाकी के पूरी तरह कार्यात्मक डेटा सरंचनाएं पुस्तक (या his dissertation (PDF) that the book is based on) को देखने के लिए है। यह हास्केल के बजाय मानक एमएल पर आधारित है, डेटा संरचनाएं समान नहीं हैं, और यह एक कठिन पढ़ा जा सकता है, लेकिन यह एक आधारभूत पुस्तक है।