सूचियों पर आगमन
यह खंड पूरा करने पर आप सिद्ध कर पाएँगे कि आपका खुद का लिखा उलटने वाला फ़ंक्शन "दो बार उलटना बराबर उलटना नहीं है" को संतुष्ट करता है। इससे भी ज़्यादा ज़रूरी बात यह है कि आप एक बार सबूत में अटकेंगे, और सीखेंगे कि जहाँ अटके हैं वहाँ से पता लगाना कि क्या कमी है।
सीखने के बाद आप क्या कर सकेंगे
- सूचियों पर आगमन-आधारित सबूत लिखें: खाली सूची, और "आगे एक तत्व जोड़ना"
- अधूरे लक्ष्य से पढ़कर पता लगाएँ कि कौन सा सहायक लेम्मा चाहिए
- पहले लेम्मा सिद्ध करें, फिर उसकी मदद से मुख्य प्रमेय पूरा करें
चरण 1: एक उलटने वाला फ़ंक्शन लिखें
def rev : List α → List α
| [] => []
| x :: xs => rev xs ++ [x][]खाली सूची है, उलटने पर भी खाली ही रहती है।x :: xsका मतलब है "पहला तत्व x, और उसके बाद सूची xs"। इसे उलटने का तरीका: पहले बाद वाले हिस्से को उलटें, फिर x को सबसे अंत में जोड़ें।++दो सूचियों को जोड़ने (concatenate) का काम करता है।
आज़माकर देखें:
#eval rev [1, 2, 3][3, 2, 1]- मेरा
rev[1, 2, 3]को उलट सकता है
चरण 2: सीधे सबूत शुरू करें, फिर अटक जाएँ
सिद्ध करना है: किसी भी सूची के लिए, rev (rev xs) = xs।
सूचियों का आगमन प्राकृतिक संख्याओं की तरह ही दो शाखाओं वाला है: nil खाली सूची है, cons x xs ih का मतलब है "x के बाद xs", और ih कहता है कि प्रस्ताव xs के लिए सही है। पिछले खंड के तरीके से लिखें:
theorem rev_rev_try (xs : List α) : rev (rev xs) = xs := by
induction xs with
| nil => rfl
| cons x xs ih => simp [rev, ih]आपको यह दिखना चाहिए: Lean बताता है कि एक अधूरा लक्ष्य बचा है:
unsolved goals
case cons
α : Type u_1
x : α
xs : List α
ih : rev (rev xs) = xs
⊢ rev (rev xs ++ [x]) = x :: xsजल्दी में रणनीति बदलने से पहले, इस लक्ष्य को ध्यान से पढ़ें। बाईं ओर rev (rev xs ++ [x]) है, यानी एक "जोड़ी हुई सूची" को उलटना। ih कहता है rev (rev xs), जिसमें बीच में एक ++ [x] अतिरिक्त है, इसलिए यह यहाँ काम नहीं आता।
जो जानकारी कमी है वह यह है: जब एक जोड़ (concatenation) को उलटते हैं तो परिणाम क्या होता है?
- मैंने
unsolved goalsदेखा, और बता सकता हूँ कि लक्ष्य औरihमें क्या अंतर है
चरण 3: पहले एक मददगार सिद्ध करें
एक ठोस उदाहरण सोचें: [1, 2] और [3, 4] को जोड़कर उलटने पर [4, 3, 2, 1] मिलता है, यानी "दूसरे आधे हिस्से का उलटा" जिसके आगे "पहले आधे हिस्से का उलटा" जुड़ा है। इसे प्रमेय के रूप में लिखें, और फिर से आगमन से सिद्ध करें:
theorem rev_append (xs ys : List α) : rev (xs ++ ys) = rev ys ++ rev xs := by
induction xs with
| nil =>
simp [rev]
| cons x xs ih =>
simp [rev, ih]मुख्य प्रमेय को सिद्ध करने के लिए पहले सिद्ध किए गए ऐसे छोटे प्रमेय को लेम्मा कहा जाता है।
rev_appendपास हो गया
चरण 4: मुख्य प्रमेय पूरा करें
लेम्मा को simp को दें:
theorem rev_rev (xs : List α) : rev (rev xs) = xs := by
induction xs with
| nil =>
rfl
| cons x xs ih =>
simp [rev, rev_append, ih]आपको यह दिखना चाहिए: कोई त्रुटि नहीं।
rev_append मिलने पर, अटा हुआ rev (rev xs ++ [x]) rev [x] ++ rev (rev xs) में बदल जाता है, और अब ih काम आ सकता है, जबकि बचा हुआ simp खुद ही पूरा कर देता है।
rev_revपास हो गया
आपकी परीक्षाप्रमाण अटक गया, Lean में unsolved goals दिखता है। अगला कदम क्या होना चाहिए?
चेकपॉइंट
- मैं सूची आगमन (induction) के दो शाखाएँ लिख सकता/सकती हूँ:
nilऔरcons x xs ih - मैं समझा सकता/सकती हूँ कि पहली कोशिश क्यों अटक गई
- मुझे पता है कि लेम्मा (lemma) क्या है, और इस खंड का लेम्मा कैसे सोचा गया था
rev_appendऔरrev_revदोनों पास हो गए
सफल नहीं हुआ?
rev_rev त्रुटि देता है कि वह rev_append को नहीं पहचानता। लेम्मा को उस थ्योरम (प्रमेय) से पहले लिखना होता है जिसमें वह उपयोग होता है। Lean फ़ाइल को ऊपर से नीचे पढ़ता है।
simp के बाद भी लक्ष्य बचा हुआ है। ऊपर दिए गए कोड से मिलाएँ, और देखें कि क्या कोष्ठकों में rev_append या ih छूट गया है।
अगला खंड
अब आप एक फ़ंक्शन सत्यापित करना जानते हैं। अंतिम खंड उन्हीं तीन चरणों — परिभाषा, अटकने पर लेम्मा खोजना, और आगमन — का उपयोग करते हुए सिद्ध करता है कि एक मिनी कंपाइलर सही है।