ہیسکل فنکشن جو دو لسٹوں کا ہیمنگ بُعْد بتاے

ہیمنگ بُعْد یہ بتاتا ہے کہ دو لسٹوں کے درمیان کتنی جگہوں پر تفاوت ہے۔ مثال کے طور پر minister اور sinister میں صرف پہلا پہلا حرف مختلف ہے۔ اس کا مطلب ہوا کہ ان دونوں کا ہیمنگ بُعْد 1 ہے۔ اسی طرح soup اور soak میں دو مقام پر فرق ہے ، ان کے درمیان ہیمنگ بُعْد ہو گا 2۔

اب ہم ایک ہیسکل فنکشن لکھیں گےجو دو لسٹوں کے مابین ہیمنگ بُعْد بتاے گا۔ ہم فرض کر لیتے ہیں کہ دونوں لسٹوں کی لمبائی برابر ہو گی۔ سب سے پہلے فنکشن کی تعریف:

hamming :: (Eq a) => [a] -> [a] -> Int

یہ سطر بتاتی ہے کہ فنکشن کا نام hamming ہے۔ یہ دو لسٹیں لیتا ہے [a] -> [a] اور ایک Intلوٹاتا ہے۔ (Eq a) بتاتا ہے کہ ان دونوں لسٹوں کے اندر جو کچھ ہے ان پر == اور /= کے آپریٹر چل سکتے ہوں، اس لیے کہ آگے چل کر ہم یہی آپریٹر استعمال کریں گے۔

اب دیکھتے ہیں کہ اس مسئلہ کو کس طرح حل کیا جاے۔ چونکہ ہم عام طور پر پروگرامنگ کے imperative اسلوب ہی سے واقف ہوتے ہیں ، اس لیے بات یہیں سے شروع کرتے ہیں۔آپ یقینا ایک لوپ لگاتے ۔ ہیمنگ بُعْد کا ریکارڈ رکھنے کے لیے کوئی variable بناتے۔ لوپ کے پہلے چکر میں دونوں لسٹوں کے پہلے پہلے حروف کا موازنہ کرتے۔ اگر دونوں مساوی نہ ہوتے تو اُس variable میں ایک جمع کرتے۔ بصورت دیگر ،کچھ کیے بغیر آگےچلتے۔ اگلے چکر میں دوسرے اور اُس سے اگلے چکر میں تیسرے حروف کا موازنہ کرتے اور اس طرح یہ سلسلہ چلتا رہتا۔

اب ہمارے پاس نہ کوئی variable ہے اور نہ ہی لوپ۔ لے دے کر ہمارے پاس رکرژن ہے اور وہ بہت کافی ہے۔ 😊 ہم ہر رکرژی قدم پر دونوں لسٹوں کا پہلا پہلا حرف الگ کر لیں گے ۔ جی ہاں، الگ کر لیں گے۔ اس طرح دونوں بقیہ لسٹوں کی لمبائی ایک ایک عددکم ہو جاے گی۔ ہیسکل میں یہ کام کرنے کا طریقہ یوں ہے:

(x:xs) (y:ys)

اب ہم دونوں حروف یعنی x اور y کا موازنہ کریں گے۔ اگر دونوں مساوی نہ ہوے تو یہ فرق کُل ہیمنگ بُعْد میں شمار ہوگا۔ کُل ہیمنگ بُعْد کا انحصار اِس فرق اور بقیہ لسٹ کے ہیمنگ بُعْد پر ہے۔ یہ بات اہم ہے۔ اس لیے اسے اچھی طرح سمجھ لیجیے۔ یوں سمجھیے کہ ہم نے مسئلہ کا سائز چھوٹا کر دیا ہے؛ البتہ مسئلہ وہی ہے۔ اس لیے ہم اسی فنکشن کو بقیہ لسٹوں کے لیے چلا دیں گے۔

hamming (x:xs) (y:ys)
| x /= y = 1 + hamming xs ys
| otherwise = 0 + hamming xs ys


اب آئیے بنیادی قدم (base case)کی طرف۔ ہر رکرژی قدم پر مسئلہ کا سائز چھوٹا ہوتا چلا جاے گا تاوقتیکہ لسٹیں خالی رہ جائیں۔ یہی ہماری بنیاد ہے۔ یہاں ہمیں رکرژن روک دینی چاہیے اور سادہ طور پر 0 لوٹا دینا چاہیے تاکہ اب تک کے گنے گئے ہیمنگ بُعْد میں کوئی اضافہ نہ ہو۔

hamming [] [] = 0

پورا کوڈ کچھ یوں ہوگا


hamming :: (Eq a) => [a] -> [a] -> Int
hamming [] [] = 0
hamming (x:xs) (y:ys)
| x /= y = 1 + hamming xs ys
| otherwise = 0 + hamming xs ys

اب آپ سوچیے کہ اگر لسٹوں کی لمبائی یکساں نہ ہوتی تو کیا ہوتا؟

Comments are closed.