इडिस

Question

में निर्भर टाइपिंग की सीमाएं मैं थोड़ी देर के लिए हास्केल लिख रहा हूं लेकिन इडिस भाषा और निर्भर टाइपिंग के साथ कुछ प्रयोगों को आजमा देना चाहता था। मैंने थोड़ा सा खेला है, और मूल दस्तावेज़ पढ़ा है, हालांकि मैं फ़ंक्शन की एक निश्चित शैली को व्यक्त करना चाहता हूं, और यह नहीं जानता कि यह कैसे संभव है।

यहाँ मैं क्या पता करने के लिए किया जाए या नहीं व्यक्त किया जा सकता इच्छा के उदाहरण के एक जोड़े हैं:

पहले: एक समारोह है कि दो प्राकृतिक संख्या लेता है, लेकिन केवल चेकों टाइप करता है, तो पहले अन्य की तुलना में छोटा होता है। तो f : Nat -> Nat -> whatever जहां nat1 nat2 से छोटा है। विचार यह है कि अगर f 5 10 जैसा कहा जाता है तो यह काम करेगा, लेकिन अगर मैंने इसे f 10 5 कहा है तो यह चेक टाइप करने में विफल रहेगा।

दूसरा: एक समारोह है कि एक स्ट्रिंग और तार कि केवल चेकों टाइप करता है, तो पहली स्ट्रिंग तार की सूची में है की एक सूची लेता है।

क्या इस तरह के कार्यों को इडिस में संभव है? यदि ऐसा है तो आप उल्लेख किए गए सरल उदाहरणों में से एक को कैसे कार्यान्वित करेंगे? धन्यवाद!

संपादित करें:

निम्नलिखित समाधान कार्यों में लिखा गया है कई उपयोगकर्ताओं की मदद से

:

module Main 

import Data.So 

f : (n : Nat) -> (m : Nat) -> {auto isLT : So (n < m)} -> Int 
f _ _ = 50 

g : (x : String) -> (xs : List String) -> {auto inIt : So (elem x xs)} -> Int 
g x xs = 52 

main : IO() 
main = putStrLn $ show $ g "hai" ["test", "yo", "ban", "hai", "dog"] 

ये वर्तमान समाधान बड़े मामलों के लिए काम नहीं करते। उदाहरण के लिए यदि आप कुछ हजारों से ऊपर संख्याओं के साथ एफ चलाते हैं तो यह हमेशा के लिए लेता है (शाब्दिक रूप से नहीं)। मुझे लगता है कि ऐसा इसलिए है क्योंकि प्रकार की जांच वर्तमान में खोज आधारित है। एक उपयोगकर्ता ने टिप्पणी की कि सबूत लिखकर ऑटो को संकेत प्रदान करना संभव है। मान लीजिए कि इन साधारण मामलों में से किसी एक के लिए कोई सबूत कैसे लिखता है?

Answer 1

I'm not especially fond of So, या वास्तव में की परिहार्य सबूत शर्तों पर सभी कार्यक्रमों में चारों ओर चल रही है। आंकड़ों के कपड़े में अपनी उम्मीदों को बुनाई करना ज्यादा संतोषजनक है। मैं n से छोटी प्राकृतिक संख्याओं के लिए एक प्रकार लिखने जा रहा हूं "।

data Fin : Nat -> Set where 
    FZ : Fin (S n) 
    FS : Fin n -> Fin (S n) 

Fin एक नंबर की तरह डेटा प्रकार है - प्राकृतिक संख्या S (S Z) के साथ FS (FS FZ) के आकार की तुलना - लेकिन कुछ अतिरिक्त प्रकार स्तरीय संरचना के साथ। इसे Fin क्यों कहा जाता है? Fin n प्रकार के अद्वितीय सदस्य हैं; Fin इस प्रकार परिमित सेट का परिवार है।

मेरा मतलब है: Fin वास्तव में एक प्रकार का नंबर है।

natToFin : (n : Nat) -> Fin (S n) 
natToFin Z = FZ 
natToFin (S k) = FS (natToFin k) 

finToNat : Fin n -> Nat 
finToNat FZ = Z 
finToNat (FS i) = S (finToNat i) 

यहाँ बात है: एक Fin n मूल्य अपनी n से छोटी होनी चाहिए।

two : Fin 3 
two = FS (FS FZ) 
two' : Fin 4 
two' = FS (FS FZ) 
badTwo : Fin 2 
badTwo = FS (FS FZ) -- Type mismatch between Fin (S n) (Type of FZ) and Fin 0 (Expected type) 

जबकि हम इसमें हैं, शून्य से कम कोई संख्या नहीं है। यही कहना है, Fin Z, 0 की कार्डिनिटी के साथ एक सेट, एक खाली सेट है।

Uninhabited (Fin Z) where 
    uninhabited FZ impossible 
    uninhabited (FS _) impossible 

आप एक संख्या है कि n की तुलना में कम है, तो यह निश्चित रूप से S n कम से कम है।

weaken : Fin n -> Fin (S n) 
weaken FZ = FZ 
weaken (FS x) = FS (weaken x) 

हम भी प्रकार चेकर का उपयोग कर स्वचालित रूप से सघनतम संभव किसी दिए गए Fin पर बाध्य लगाने के लिए अन्य तरीके से जा सकते हैं,: हम इस तरह एक Fin पर ऊपरी सीमा ढीला करने का एक तरीका है।

strengthen : (i : Fin n) -> Fin (S (finToNat i)) 
strengthen FZ = FZ 
strengthen (FS x) = FS (strengthen x) 

एक सुरक्षित रूप से Nat संख्या कि बड़े होते हैं से Fin संख्या के घटाव परिभाषित कर सकते हैं। हम इस तथ्य को भी व्यक्त कर सकते हैं कि परिणाम इनपुट से बड़ा नहीं होगा।

(-) : (n : Nat) -> Fin (S n) -> Fin (S n) 
n - FZ = natToFin n 
(S n) - (FS m) = weaken (n - m) 

---

बस इतना ही काम करता है, लेकिन वहाँ एक समस्या है: हे (एन) समय में अपने तर्क के पुनर्निर्माण द्वारा weaken काम करता है, और हम - के हर पुनरावर्ती कॉल पर यह लागू कर रहे हैं, एक ओ उपज (एन^2) घटाव के लिए एल्गोरिदम। कितना शर्मनाक है! weaken टाइप-चेकिंग में मदद करने के लिए वास्तव में वास्तव में है, लेकिन कोड की एसिम्प्टोटिक समय जटिलता पर इसका एक कठोर प्रभाव पड़ता है। क्या हम रिकर्सिव कॉल के नतीजे कमजोर किए बिना दूर हो सकते हैं?

ठीक है, हमें weaken पर कॉल करना पड़ा क्योंकि हर बार हमें S का सामना करना पड़ता है, परिणाम और बाध्यता के बीच का अंतर बढ़ता है। सही प्रकार तक मूल्य को मजबूती से यंक करने के बजाय, हम इसे पूरा करने के लिए धीरे-धीरे नीचे खींचकर अंतराल को बंद कर सकते हैं।

(-) : (n : Nat) -> (i : Fin (S n)) -> Fin (S (n `sub` finToNat i)) 
n - FZ = natToFin n 
(S n) - (FS i) = n - i 

इस प्रकार का एक Fin के strengthen साथ बाध्य कस में हमारी सफलता से प्रेरित है। - के परिणाम पर बाध्य बिल्कुल उतना ही तंग है जितना कि इसकी आवश्यकता है।

sub, जो मैंने इस प्रकार उपयोग किया है, प्राकृतिक संख्याओं का घटाव है। तथ्य यह है कि यह शून्य पर छेड़छाड़ करने की आवश्यकता नहीं है, क्योंकि - का प्रकार यह सुनिश्चित करता है कि यह वास्तव में कभी नहीं होगा। (यह समारोह minus के नाम के तहत Prelude में पाया जा सकता है।)

sub : Nat -> Nat -> Nat 
sub n Z = n 
sub Z m = Z 
sub (S n) (S m) = sub n m 

सबक यहाँ सीखा जा करने के लिए इस है। सबसे पहले, हमारे डेटा में कुछ शुद्धता गुणों का निर्माण करने से एसिम्प्टोटिक मंदी हुई। हम वापसी मूल्य के बारे में वादे करने के लिए छोड़ दिया था और एक untyped संस्करण पर वापस चला गया, लेकिन वास्तव में giving the type checker more information हमें यह बताने की अनुमति दी कि हम बलिदान किए बिना कहाँ जा रहे थे।