ہیسکل فنکشن جو بتاے کہ دی گئی لسٹ پیلنڈروم ہے یا نہیں

آج ہم ایک سادہ سا ہیسکل فنکشن لکھیں گے۔ یہ فنکشن ایک [Char] یا String لے گا اور بتاے گا کہ وہ palindrome[1]مَقلُوب ِمُستَوی ہے یا نہیں۔

isPalindrome :: [Char] -> Bool

ہم جانتے ہیں کہ وہ کام جو ++C یا Java میں لوپ[2]گردش کے ذریعے کیے جاتے ہیں، ان کو ہیسکل میں رِکرژن کے ذریعے کیا جاے گا۔

سوچیے کہ اگر ہم لوپ استعمال کر سکتے تو کیا کرتے؟ یعنی لوپ کے ہر چکر میں کیا کرتے؟ یہی نا کہ پہلے حرف کا آخری حرف سے موازنہ کرتے۔ اگر دونوں حروف ایک سے نہ ہوتے تو لوپ توڑ دیتے اور کہہ دیتے کہ یہ لسٹ palindrome نہیں! اور اگر دونوں ایک جیسے ہوتے تو اگلے چکر میں پہلے حرف سے اگلے اور آخری سے پچھلے کا موازنہ کرتے اور یہ سلسلہ اسی طرح چلتا رہتا۔

اب یہی موازنہ ہم رکرژن کے ہر قدم پر کریں گے۔ اس کو اس طرح سوچیے کہ ہر قدم پر ہم لسٹ سے پہلا اور آخری حرف نکال لیتے ہیں اور ان کا موازنہ کرتے ہیں۔ مزید یہ کہ لسٹ بھی چھوٹی ہوجاتی ہے۔ اس طرح سوچنے کا فائدہ یہ ہے کہ اگلے رکرثی قدم پر بھی ہم نئی لسٹ کے پہلے اور آخری حرف ہی کا موازنہ کر رہے ہوں گے۔

isPalindrome (x:xs) = if x /= last xs then False else isPalindrome (init xs)

جہاں رکرژن کا ذکر آے گا وہاں بنیادی قدم (Base Case) کا ذکر بھی آے گا۔ اب یہ سوچیے کہ اگر لسٹ واقعی palindrome ہو تو رکرژن کہاں جا کر رکے گی؟ لسٹ میں حروف کی تعداد جفت (even) ہوگی یا طاق(odd)۔ اگر جفت ہو گی تو اس صورت میں اوپر بیان کی گئی لاجک کام کرے گی۔ البتہ آخری قدم پر لسٹ خالی رہ جاے گی۔ تو ہمیں خالی لسٹ کو palindrome مانتے ہوے True لوٹا دینا چاہیے۔

isPalindrome [] = True

اگر حروف کی تعداد طاق ہو تو آخری قدم پر ہمارے پاس ایک ہی حرف ہوگا جس کو ہم palindrome مانتے ہوے True لوٹا دیں گے۔

isPalindrome (x:[]) = True

پورا کوڈ کچھ اس طرح کا ہوگا

isPalindrome :: String -> Bool
isPalindrome [] = True
isPalindrome (x:[]) = True
isPalindrome (x:xs) = if x /= last xs then False else isPalindrome (init xs)

:اس کوڈ کی آخری سطر کو مزید بہتر کیا جا سکتا ہے

isPalindrome xs = head xs == last xs && isPalindrome ( tail ( init xs ))

اب اسی مسئلہ پر ایک اور طرح سوچیے: پیلنڈروم وہ اسٹرنگ ہے جس کو الٹا دیا جاے تب بھی وہ ویسی ہی رہے

References

References
1 مَقلُوب ِمُستَوی
2 گردش

Comments are closed.