haskell - today - हाउ तो वोट#इंडिया डेट



हमें कंटेनरों की आवश्यकता क्यों है? (1)

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

कंटेनर: एक सैद्धांतिक उपकरण, एक अच्छा रन-टाइम डेटा प्रतिनिधित्व रणनीति नहीं

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

शब्दावली को ठीक करने के लिए, हम कहते हैं कि कंटेनर का प्रकार ( Set पर, लेकिन अन्य श्रेणियां उपलब्ध हैं) एक कंस्ट्रक्टर द्वारा दिया गया है <| पैकिंग दो क्षेत्रों, आकार और पदों

S : Set
P : S -> Set

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

एक फ़नकार के रूप में इस तरह की चीज़ की व्याख्या इसके द्वारा दी गई है

[_]C : Cont -> Set -> Set
[ S <| P ]C X = Sg S \ s -> P s -> X  -- I'd prefer (s : S) * (P s -> X)
mapC : (C : Cont){X Y : Set} -> (X -> Y) -> [ C ]C X -> [ C ]C Y
mapC (S <| P) f (s , k) = (s , f o k)  -- o is composition

और हम पहले से ही जीत रहे हैं। यह map सभी के लिए एक बार लागू किया गया है। क्या अधिक है, अकेले मज़दूर द्वारा मज़ेदार कानून बनाए जाते हैं। ऑपरेशन का निर्माण करने के लिए, या कानूनों को साबित करने के लिए प्रकारों की संरचना पर पुनरावृत्ति की आवश्यकता नहीं है।

विवरण असामान्य रूप से कंटेनर हैं

कोई भी यह दावा करने का प्रयास नहीं कर रहा है कि, परिचालन, Nat <| Fin Nat <| Fin सूचियों का कुशल कार्यान्वयन करता है, बस उस पहचान को बनाकर हम सूचियों की संरचना के बारे में कुछ उपयोगी सीखते हैं।

मुझे वर्णनों के बारे में कुछ कहने दें। आलसी पाठकों के लाभ के लिए, मुझे उनका पुनर्निर्माण करना चाहिए।

data Desc : Set1 where
  var : Desc
  sg pi  : (A : Set)(D : A -> Desc) -> Desc
  one : Desc                    -- could be Pi with A = Zero
  _*_ : Desc -> Desc -> Desc    -- could be Pi with A = Bool

con : Set -> Desc   -- constant descriptions as singleton tuples
con A = sg A \ _ -> one

_+_ : Desc -> Desc -> Desc   -- disjoint sums by pairing with a tag
S + T = sg Two \ { true -> S ; false -> T }

Desc में मान उन फंक्शंस का वर्णन करते हैं जिनके फ़िक्सप्वाइंट डेटाैटिप्स देते हैं। वे कौन से फंक्शनलर्स का वर्णन करते हैं?

[_]D : Desc -> Set -> Set
[ var    ]D X = X
[ sg A D ]D X = Sg A \ a -> [ D a ]D X
[ pi A D ]D X = (a : A) -> [ D a ]D X
[ one    ]D X = One
[ D * D' ]D X = Sg ([ D ]D X) \ _ -> [ D' ]D X

mapD : (D : Desc){X Y : Set} -> (X -> Y) -> [ D ]D X -> [ D ]D Y
mapD var      f x        = f x
mapD (sg A D) f (a , d)  = (a , mapD (D a) f d)
mapD (pi A D) f g        = \ a -> mapD (D a) f (g a)
mapD one      f <>       = <>
mapD (D * D') f (d , d') = (mapD D f d , mapD D' f d')

हमें अनिवार्य रूप से विवरणों पर पुनरावृत्ति द्वारा काम करना है, इसलिए यह कठिन काम है। फ़नकारक कानून भी, मुफ्त में नहीं आते हैं। हमें डेटा का एक बेहतर प्रतिनिधित्व प्राप्त होता है, ऑपरेशनली, क्योंकि कंक्रीट ट्यूप्स करते समय हमें कार्यात्मक एनकोडिंग का सहारा लेने की आवश्यकता नहीं होती है। लेकिन हमें प्रोग्राम लिखने के लिए अधिक मेहनत करनी होगी।

ध्यान दें कि हर कंटेनर में एक विवरण होता है:

sg S \ s -> pi (P s) \ _ -> var

लेकिन यह भी सच है कि प्रत्येक विवरण में एक आइसोमोर्फिक कंटेनर के रूप में एक प्रस्तुति है

ShD  : Desc -> Set
ShD D = [ D ]D One

PosD : (D : Desc) -> ShD D -> Set
PosD var      <>       = One
PosD (sg A D) (a , d)  = PosD (D a) d
PosD (pi A D) f        = Sg A \ a -> PosD (D a) (f a)
PosD one      <>       = Zero
PosD (D * D') (d , d') = PosD D d + PosD D' d'

ContD : Desc -> Cont
ContD D = ShD D <| PosD D

यह कहना है, कंटेनर विवरण के लिए एक सामान्य रूप है। यह दिखाने के लिए एक अभ्यास है कि [ D ]DX स्वाभाविक रूप से [ ContD D ]CX को समरूप है। यह जीवन को आसान बनाता है, क्योंकि कहने के लिए कि विवरण के लिए क्या करना है, यह सिद्धांत रूप में यह कहने के लिए पर्याप्त है कि उनके सामान्य रूपों, कंटेनरों के लिए क्या करना है। उपरोक्त mapD ऑपरेशन, सिद्धांत रूप में, mapC की समरूप परिभाषा में आइसोमोर्फिम्स को फ्यूज करके प्राप्त किया जा सकता है।

विभेदक संरचना: कंटेनर रास्ता दिखाते हैं

इसी तरह, अगर हमारे पास समानता की धारणा है, तो हम कह सकते हैं कि एक-छेद वाले संदर्भ कंटेनरों के लिए समान रूप से क्या हैं

_-[_] : (X : Set) -> X -> Set
X -[ x ] = Sg X \ x' -> (x == x') -> Zero

dC : Cont -> Cont
dC (S <| P) = (Sg S P) <| (\ { (s , p) -> P s -[ p ] })

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

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

dD : Desc -> Desc
dD var = one
dD (sg A D) = sg A \ a -> dD (D a)
dD (pi A D) = sg A \ a -> (pi (A -[ a ]) \ { (a' , _) -> D a' }) * dD (D a)
dD one      = con Zero
dD (D * D') = (dD D * D') + (D * dD D')

मैं कैसे जांच सकता हूं कि विवरण के लिए मेरा व्युत्पन्न ऑपरेटर सही है? कंटेनरों के व्युत्पन्न के खिलाफ इसकी जाँच करके!

इस सोच के जाल में मत पड़ो कि सिर्फ इसलिए कि किसी विचार की प्रस्तुति परिचालन रूप से सहायक नहीं है कि वह वैचारिक रूप से मददगार नहीं हो सकती।

"फ्रीर" भिक्षुओं पर

एक अंतिम बात। Freer ट्रिक राशियों को एक विशेष तरीके से एक मनमाने फ़ंक्टर को फिर से व्यवस्थित करने के लिए (हास्केल पर स्विच करना)

data Obfuncscate f x where
  (:<) :: forall p. f p -> (p -> x) -> Obfuncscate f x

लेकिन यह कंटेनरों का विकल्प नहीं है। यह एक कंटेनर प्रस्तुति की थोड़ी सी करी है। यदि हमारे पास मजबूत अस्तित्व और निर्भरता के प्रकार थे, तो हम लिख सकते थे

data Obfuncscate f x where
  (:<) :: pi (s :: exists p. f p) -> (fst s -> x) -> Obfuncscate f x

इसलिए कि (exists p. fp) आकृतियों का प्रतिनिधित्व करता है (जहां आप अपनी स्थिति का प्रतिनिधित्व चुन सकते हैं, फिर प्रत्येक स्थान को उसकी स्थिति के साथ चिह्नित कर सकते हैं), और एक आकार से अस्तित्व के गवाह को चुनता है (आपके द्वारा चुना गया पोजीशन प्रतिनिधित्व)। यह बिल्कुल स्पष्ट रूप से सकारात्मक होने का गुण है क्योंकि यह एक कंटेनर प्रस्तुति है।

हास्केल में, निश्चित रूप से, आपको अस्तित्व के बारे में पता लगाना होगा, जो सौभाग्य से केवल प्रकार के प्रक्षेपण पर निर्भरता छोड़ देता है। यह अस्तित्व की कमजोरी है जो Obfuncscate f और f के तुल्यता को सही ठहराती है। यदि आप मजबूत अस्तित्व के साथ एक निर्भर प्रकार के सिद्धांत में एक ही चाल की कोशिश करते हैं, तो एन्कोडिंग अपनी विशिष्टता खो देता है क्योंकि आप पदों के लिए प्रतिनिधित्व के विभिन्न विकल्पों को प्रोजेक्ट और बता सकते हैं। यही है, मैं Just 3 प्रतिनिधित्व कर सकता हूं

Just () :< const 3

या द्वारा

Just True :< \ b -> if b then 3 else 5

और Coq में, कहते हैं, ये काफी अलग हैं।

चुनौती: बहुरूपी कार्यों को चिह्नित करना

कंटेनर प्रकारों के बीच हर बहुरूपी कार्य एक विशेष तरीके से दिया जाता है। हमारी समझ को फिर से स्पष्ट करने के लिए काम करने वाली एकरूपता है।

अगर आपके पास कुछ है

f : {X : Set} -> [ S <| T ]C X -> [ S' <| T' ]C X

यह (एक्सटेंसिक रूप से) निम्न डेटा द्वारा दिया गया है, जो तत्वों का कोई उल्लेख नहीं करता है:

toS    : S -> S'
fromP  : (s : S) -> P' (toS s) -> P s

f (s , k) = (toS s , k o fromP s)

यही है, कंटेनरों के बीच एक बहुरूपी फ़ंक्शन को परिभाषित करने का एकमात्र तरीका यह है कि इनपुट आकृतियों को आउटपुट आकृतियों में कैसे अनुवाद किया जाए, फिर यह कहें कि इनपुट पदों से आउटपुट पदों को कैसे भरें।

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

चुनौती: कैप्चरिंग "ट्रांसपोज़िबिलिटी"

दो फ़ंक्शनलर्स, f और g को देखते हुए, यह कहना आसान है कि उनकी रचना fog क्या है: (fog) x f (gx) में चीजों को लपेटता है f (gx) , जिससे हमें " g रुचियों का अवरोधक" मिलता है। लेकिन क्या आप आसानी से अतिरिक्त स्थिति को लागू कर सकते हैं कि g संरचना में संग्रहीत सभी संरचनाओं का आकार समान है?

मान लीजिए कि f >< g fog के ट्रांसपेरेंट टुकड़े को पकड़ लेता है, जहां सभी g आकार एक समान होते हैं, ताकि हम बस इस चीज को g बाधा के g बाधा में बदल सकें। जैसे, जबकि [] o [] सूचियों की चीर-फाड़ करता है, [] >< [] आयताकार मैट्रीक देता है; [] >< Maybe सूची देता है जो या तो कुछ Nothing या सभी Just

सख्ती से सकारात्मक फंक्शनलर्स के अपने पसंदीदा प्रतिनिधित्व के लिए दे >< । कंटेनरों के लिए, यह आसान है।

(S <| P) >< (S' <| P') = (S * S') <| \ { (s , s') -> P s * P' s' }

निष्कर्ष

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

(एक बहाने के रूप में: शीर्षक शीर्षक की नकल करता है कि हमें भिक्षुओं की आवश्यकता क्यों है? )

containers (और indexed वाले) (और hasochistic वाले) और descriptions । लेकिन कंटेनर problematic और मेरे बहुत छोटे अनुभव से वर्णन के संदर्भ में कंटेनरों के संदर्भ में सोचना कठिन है। गैर-अनुक्रमित कंटेनरों का प्रकार or के लिए आइसोमोर्फिक है - यह काफी अनिर्दिष्ट है। आकार-और-स्थिति विवरण मदद करता है, लेकिन अंदर

⟦_⟧ᶜ :   β γ} -> Container α β -> Set γ -> Set   β  γ)
 Sh  Pos ⟧ᶜ A =  λ sh -> Pos sh -> A

K :   β} -> Set α -> Container α β
K A = A  const (Lift ⊥)

हम अनिवार्य रूप से आकार और स्थिति के बजाय Σ का उपयोग कर रहे हैं।

कंटेनरों पर कड़ाई से पॉजिटिव फ्री मोनाड्स के प्रकार की सीधी-सादी परिभाषा है, लेकिन Freer मोनाड्स का प्रकार मुझे सरल लगता है (और एक अर्थ में Freer मोनाडर्स सामान्य Free मोनडर्स से भी बेहतर हैं जैसा कि paper में वर्णित है)।

तो हम वर्णन या कुछ और के साथ एक अच्छे तरीके से कंटेनरों के साथ क्या कर सकते हैं?





type-theory