कार्यात्मक लिंक्ड सूची

क्लोजर के माध्यम से लिंक की गई सूचियों के कार्यान्वयन पर विचार करें।

सूचियों को निरूपित करने के लिए, हम हास्केल: x:xs समान एक अंकन का उपयोग करेंगे, जहां x सूची ( head ) की शुरुआत है, xs निरंतरता ( tail ) है।



मैंने जावास्क्रिप्ट को कार्यान्वयन भाषा के रूप में चुना।

एक सूची का निर्माण

लिंक की गई सूचियों के साथ काम करने के लिए, निम्नलिखित मूल प्राथमिकताओं की आवश्यकता होती है: nil - एक खाली सूची, prepend ( cons ) - सूची, head और tail के शीर्ष पर सम्मिलित फ़ंक्शन।

दो मदों की सूची बनाना इस प्रकार है:

 prepend('a', prepend('b', nil)) // 'a' -> 'b' -> nil 

prepend फ़ंक्शन का कार्यान्वयन:

 function prepend(x, xs) { return function (select) { return select(x, xs) } } 

मुफ्त चर ( x:xs ) तक पहुंचने के लिए select फ़ंक्शन की आवश्यकता है।

वांछित select मूल्य के साथ सूची फ़ंक्शन को कॉल करने के लिए head और tail का कार्यान्वयन उबलता है:

 function select_head(x, xs) { return x } function select_tail(x, xs) { return xs } function head(a) { return a(select_head) } function tail(a) { return a(select_tail) } 

यह एक खाली सूची ( nil ) को लागू करने के लिए बनी हुई है:

 function nil() { return nil } 

तो head(nil) === tail(nil) === nil ।

उदाहरण का उपयोग करें

एक सूची के निर्माण और ट्रैवर्सल को दर्शाने वाला एक सरल कार्यक्रम:

 var a = prepend('a', prepend('b', nil)) // 'a' -> 'b' -> nil head(a) // => 'a' head(tail(a)) // => 'b' head(tail(tail(a))) // => nil while (a !== nil) { console.log(head(a)) a = tail(a) } 

उच्च आदेश कार्य

परिणामी डेटा संरचना के लिए, उच्च-क्रम के कार्यों को लागू किया जा सकता है, उदाहरण के लिए, map :

 function map(fn, a) { if (a === nil) return nil return prepend(fn(head(a)), map(fn, tail(a))) } 

यह हमें एक कार्यात्मक शैली में हमारी सूचियों के साथ काम करने की अनुमति देगा:

 var a = prepend(1, prepend(2, prepend(3, nil))) // 1 -> 2 -> 3 -> nil function power_of_2(x) { return 1 << x } var b = map(power_of_2, a) // 2 -> 4 -> 8 -> nil 

अन्य जुड़े कार्यों ( filter , reduce ) को होमवर्क के रूप में पाठक को पेश किया जाता है।

ऐसी बातें ™

एक लेख लिखते समय, एक भी सरणी क्षतिग्रस्त नहीं हुई थी।

रोटी से एक ट्रॉली की तस्वीर की आशंका : यह निश्चित रूप से एक लागू समाधान नहीं है। इसके अलावा, इस तरह के एक काम के लिए, वे आसानी से और अनर्गल रूप से अपने हाथों को फाड़ सकते हैं। इस ज्ञान के साथ आगे क्या करना है आप पर निर्भर है।

जीथुब: github.com/mvasilkov/functional-js