Purely functional data structure
کمپیوٹر سائنس میں، خالصتا فنکشنل ڈیٹا اسٹرکچر ایک ڈیٹا اسٹرکچر ہے جسے خالصتا فنکشنل زبان میں براہ راست لاگو کیا جا سکتا ہے۔ صوابدیدی ڈیٹا ڈھانچے اور خالص طور پر فعال ڈھانچے کے درمیان بنیادی فرق یہ ہے کہ مؤخر الذکر (مضبوطی سے) غیر متغیر ہے۔ یہ پابندی اس بات کو یقینی بناتی ہے کہ ڈیٹا ڈھانچہ غیر متغیر اشیاء کے فوائد رکھتا ہے: (مکمل) تسلسل، اشیاء کی فوری کاپی، اور دھاگے کی حفاظت۔ موثر خالص طور پر فعال ڈیٹا ڈھانچے کے لیے سست تشخیص اور یادداشت کے استعمال کی ضرورت پڑ سکتی ہے۔ تعریف مستقل ڈیٹا ڈھانچے میں اپنے پچھلے ورژن کو غیر تبدیل شدہ رکھنے کی خاصیت ہوتی ہے۔ دوسری طرف، صفوں جیسے ڈھانچے ایک تباہ کن اپ ڈیٹ کو تسلیم کرتے ہیں، یعنی ایک اپ ڈیٹ جسے الٹا نہیں کیا جا سکتا۔ ایک بار جب کوئی پروگرام صف کے کسی اشاریہ میں قدر لکھ دیتا ہے، تو اس کی پچھلی قدر کو اب بازیافت نہیں کیا جا سکتا۔ رسمی طور پر، خالص طور پر فنکشنل ڈیٹا اسٹرکچر ایک ڈیٹا اسٹرکچر ہے جسے خالص طور پر فنکشنل زبان میں لاگو کیا جا سکتا ہے، جیسے کہ ہاسکل۔ عملی طور پر، اس کا مطلب یہ ہے کہ ڈیٹا ڈھانچے کو صرف مستقل ڈیٹا ڈھانچے جیسے ٹپل، سم کی اقسام، پروڈکٹ کی اقسام، اور بنیادی اقسام جیسے انٹیجرز، حروف، سٹرنگز کا استعمال کرتے ہوئے بنایا جانا چاہیے۔ اس طرح کا ڈیٹا ڈھانچہ لازمی طور پر مستقل ہے۔ تاہم، تمام مستقل ڈیٹا ڈھانچے خالصتا فعال نہیں ہیں۔ مثال کے طور پر، مستقل صف ایک ڈیٹا ڈھانچہ ہے جو مستقل ہے اور جسے صف کا استعمال کرتے ہوئے نافذ کیا جاتا ہے، اس طرح یہ خالصتا فعال نہیں ہے۔ خالص فنکشنل ڈیٹا اسٹرکچرز نامی کتاب میں، اوکاساکی نے تباہ کن اپ ڈیٹس کا موازنہ ماسٹر شیف کے چاقو سے کیا ہے۔ تباہ کن اپ ڈیٹس کو کالعدم نہیں کیا جا سکتا، اور اس طرح انہیں اس وقت تک استعمال نہیں کیا جانا چاہیے جب تک کہ یہ یقینی نہ ہو کہ پچھلی قیمت کی مزید ضرورت نہیں ہے۔ تاہم، تباہ کن اپ ڈیٹس کارکردگی کی بھی اجازت دے سکتی ہیں جو دوسری تکنیکوں کا استعمال کرتے ہوئے حاصل نہیں کی جا سکتی ہیں۔ مثال کے طور پر، ایک صف اور تباہ کن اپ ڈیٹس استعمال کرنے والے ڈیٹا ڈھانچے کو اسی طرح کے ڈیٹا ڈھانچے سے تبدیل کیا جا سکتا ہے جہاں صف کو نقشے، بے ترتیب رسائی کی فہرست، یا متوازن درخت سے تبدیل کیا جاتا ہے، جو خالصتا فعال نفاذ کو تسلیم کرتا ہے۔ لیکن رسائی کی لاگت مستقل وقت سے لے کر لوگرتھمک وقت تک بڑھ سکتی ہے۔ اس بات کو یقینی بنانا کہ ڈیٹا ڈھانچہ خالصتا فعال ہے۔ ڈیٹا ڈھانچہ کبھی بھی فطری طور پر فعال نہیں ہوتا ہے۔ مثال کے طور پر، ایک اسٹیک کو سنگل لنکڈ لسٹ کے طور پر لاگو کیا جا سکتا ہے۔ یہ عمل درآمد خالصتا فعال ہے جب تک کہ اسٹیک پر موجود واحد آپریشن پرانے اسٹیک کو تبدیل کیے بغیر ایک نیا اسٹیک واپس کرے۔ تاہم، اگر زبان خالصتا فعال نہیں ہے، تو رن ٹائم سسٹم عدم استحکام کی ضمانت دینے سے قاصر ہو سکتا ہے۔ اس کی مثال اوکاساکی نے دی ہے، جہاں وہ دکھاتا ہے کہ دو واحد منسلک فہرستوں کا مجموعہ اب بھی ایک لازمی ترتیب کا استعمال کرتے ہوئے کیا جا سکتا ہے۔ اس بات کو یقینی بنانے کے لیے کہ ڈیٹا ڈھانچہ خالصتا فعال طریقے سے ایک ناپاک فعال زبان میں استعمال کیا جاتا ہے، ماڈیولز یا کلاسز کو صرف مجاز افعال کے ذریعے ہیرا پھیری کو یقینی بنانے کے لیے استعمال کیا جا سکتا ہے۔ خالص طور پر فنکشنل ڈیٹا ڈھانچے کا استعمال خالص طور پر فنکشنل ڈیٹا ڈھانچے کو استعمال کرنے کے لیے موجودہ کوڈ کو اپنانے میں مرکزی چیلنجوں میں سے ایک اس حقیقت میں مضمر ہے کہ متغیر ڈیٹا ڈھانچے ان افعال کے لیے "پوشیدہ آؤٹ پٹ" فراہم کرتے ہیں جو انہیں استعمال کرتے ہیں۔ خالص طور پر فنکشنل ڈیٹا ڈھانچے کو استعمال کرنے کے لیے ان افعال کو دوبارہ لکھنے کے لیے ان ڈیٹا ڈھانچوں کو واضح آؤٹ پٹ کے طور پر شامل کرنے کی ضرورت ہوتی ہے۔ مثال کے طور پر، ایک ایسے فنکشن پر غور کریں جو متغیر فہرست کو قبول کرتا ہے، فہرست سے پہلا عنصر ہٹا دیتا ہے، اور اس عنصر کو واپس کرتا ہے۔ خالص طور پر فعال ترتیب میں، فہرست سے کسی عنصر کو ہٹانے سے ایک نئی اور مختصر فہرست تیار ہوتی ہے، لیکن اصل کو اپ ڈیٹ نہیں کرتا ہے۔ مفید ہونے کے لیے، اس فنکشن کے خالص فعال ورژن کو ہٹائے گئے عنصر کے ساتھ نئی فہرست واپس کرنے کا امکان ہے۔ سب سے عام صورت میں، اس طرح سے تبدیل شدہ پروگرام کو ہر فنکشن کال کے اضافی نتیجے کے طور پر پروگرام کی "اسٹیٹ" یا "اسٹور" کو واپس کرنا ہوگا۔ کہا جاتا ہے کہ اس طرح کا پروگرام اسٹور پاسنگ انداز میں لکھا جاتا ہے۔ تجریدی ڈیٹا ڈھانچوں کی فہرست یہاں خالص طور پر فعال نفاذ کے ساتھ ہے: اسٹیک (فرسٹ ان، لاسٹ آؤٹ) جسے سنگل لنکڈ لسٹ کے طور پر لاگو کیا گیا ہے، قطار، جسے ریئل ٹائم قطار کے طور پر لاگو کیا گیا ہے، ڈبل اینڈڈ قطار، جسے ریئل ٹائم ڈبل اینڈڈ قطار کے طور پر لاگو کیا گیا ہے، (ملٹی) ترتیب شدہ عناصر کا سیٹ اور ترتیب دی گئی چابیاں کے ذریعے انڈیکس شدہ نقشہ، جسے ریڈ بلیک ٹری کے طور پر لاگو کیا گیا ہے، یا زیادہ عام طور پر سرچ ٹری کے ذریعے، ترجیحی قطار، جسے بروڈل قطار بے ترتیب رسائی کی فہرست کے طور پر لاگو کیا گیا ہے، جسے اسکیو بائنری بے ترتیب رسائی کی فہرست کے طور پر لاگو کیا گیا ہے۔ ہیش کنسنگ زیپر (ڈیٹا ڈھانچہ) ڈیزائن اور نفاذ اپنی کتاب خالص فنکشنل ڈیٹا ڈھانچے میں، کمپیوٹر سائنسدان کرس اوکاساکی نے خالص طور پر فعال ڈیزائن اور لاگو کرنے کے لیے استعمال ہونے والی تکنیکوں کو بیان کیا ہے۔ سستی تشخیص خالصتا فنکشنل زبان میں خاص طور پر دلچسپ ہے کیونکہ تشخیص کی ترتیب کبھی بھی فنکشن کے نتائج کو تبدیل نہیں کرتی ہے۔ لہذا، سست تشخیص قدرتی طور پر خالص طور پر فعال ڈیٹا ڈھانچے کی تعمیر کا ایک اہم حصہ بن جاتا ہے۔ یہ کمپیوٹیشن کو صرف اس صورت میں کرنے کی اجازت دیتا ہے جب اس کا نتیجہ اصل میں درکار ہو۔ لہذا، خالص طور پر فعال ڈیٹا ڈھانچے کا کوڈ، کارکردگی کے نقصان کے بغیر، اسی طرح کے ڈیٹا پر غور کر سکتا ہے جو مؤثر طریقے سے استعمال کیا جائے گا اور ڈیٹا جسے نظر انداز کیا جائے گا۔ پہلی قسم کے ڈیٹا کے لیے صرف کمپیوٹیشن کی ضرورت ہوتی ہے ؛ یہ وہی ہے جو اصل میں انجام دیا جائے گا۔ موثر، خالص طور پر فعال ڈیٹا ڈھانچے کی تعمیر میں کلیدی ٹولز میں سے ایک میموائزیشن ہے۔ جب حساب کتاب کیا جاتا ہے، تو اسے محفوظ کیا جاتا ہے اور اسے دوسری بار انجام دینے کی ضرورت نہیں ہوتی ہے۔ یہ سست نفاذ میں خاص طور پر اہم ہے ؛ اضافی تشخیص کے لیے ایک ہی نتیجہ درکار ہو سکتا ہے، لیکن یہ جاننا ناممکن ہے کہ کس تشخیص کے لیے پہلے اس کی ضرورت ہوگی۔ کچھ ڈیٹا ڈھانچے، یہاں تک کہ وہ جو خالص طور پر فعال نہیں ہیں جیسے کہ متحرک صف، ان کارروائیوں کو تسلیم کرتے ہیں جو زیادہ تر وقت موثر ہوتے ہیں (مثال کے طور پر، متحرک صفوں کے لیے مستقل وقت)، اور شاذ و نادر ہی غیر موثر (مثال کے طور پر، متحرک صفوں کے لیے لکیری وقت)۔ اس کے بعد ادائیگی کا استعمال یہ ثابت کرنے کے لیے کیا جا سکتا ہے کہ کارروائیوں کا اوسط چلنے کا وقت موثر ہے۔ یہ کہنا ہے کہ چند غیر موثر کارروائیاں کافی کم ہوتی ہیں، اور جب کارروائیوں کے سلسلے پر غور کیا جاتا ہے تو وقت کی پیچیدگی کے غیر علامتی ارتقاء کو تبدیل نہیں کرتے ہیں۔ عام طور پر، مستقل ڈیٹا ڈھانچے کے لیے غیر موثر کارروائیوں کا ہونا قابل قبول نہیں ہے، کیونکہ اسی عمل کو کئی بار کہا جا سکتا ہے۔ یہ یا تو حقیقی وقت کے لیے یا لازمی نظاموں کے لیے قابل قبول نہیں ہے، جہاں صارف کو آپریشن کے ذریعے لیے گئے وقت کی پیش گوئی کرنے کی ضرورت پڑ سکتی ہے۔ مزید برآں، یہ غیر متوقعیت متوازی کے استعمال کو پیچیدہ بناتی ہے۔ ان مسائل سے بچنے کے لیے، کچھ ڈیٹا ڈھانچے غیر موثر آپریشن کو ملتوی کرنے کی اجازت دیتے ہیں-اسے شیڈولنگ کہا جاتا ہے۔ واحد ضرورت یہ ہے کہ ناکارہ عمل کی گنتی اس سے پہلے ختم ہو جانی چاہیے کہ اس کے نتیجے کی حقیقت میں ضرورت ہو۔ غیر موثر آپریشن کا ایک مستقل حصہ ایک موثر آپریشن کے لیے درج ذیل کال کے ساتھ بیک وقت انجام دیا جاتا ہے، تاکہ ضرورت پڑنے پر غیر موثر آپریشن پہلے ہی مکمل طور پر ہو جائے، اور ہر انفرادی آپریشن موثر رہے۔ مثال: قطار قابل ادائیگی قطاریں دو واحد منسلک فہرستوں پر مشتمل ہوتی ہیں: اگلا اور الٹا پچھلا۔ عناصر کو پچھلی فہرست میں شامل کیا جاتا ہے اور اگلی فہرست سے ہٹا دیا جاتا ہے۔ مزید برآں، جب بھی اگلی قطار خالی ہوتی ہے، تو پچھلی قطار الٹ جاتی ہے اور اگلی بن جاتی ہے، جبکہ پچھلی قطار خالی ہو جاتی ہے۔ ہر آپریشن کی تخفیف شدہ وقت کی پیچیدگی مستقل ہے۔ فہرست کے ہر سیل کو زیادہ سے زیادہ ایک بار شامل، الٹا اور ہٹا دیا جاتا ہے۔ ایک غیر موثر آپریشن سے بچنے کے لیے جہاں پچھلی فہرست الٹ جاتی ہے، حقیقی وقت کی قطاریں اس پابندی کو شامل کرتی ہیں کہ پچھلی فہرست صرف اگلی فہرست جتنی لمبی ہوتی ہے۔ اس بات کو یقینی بنانے کے لیے کہ پچھلی فہرست اگلی فہرست سے لمبی ہو جائے، اگلی فہرست کو پچھلی فہرست میں شامل کیا جاتا ہے اور الٹ دیا جاتا ہے۔ چونکہ یہ آپریشن ناکارہ ہے، اس لیے اسے فوری طور پر انجام نہیں دیا جاتا۔ اس کے بجائے، یہ بعد کی کارروائیوں میں پھیلا ہوا ہے۔ اس طرح، ہر سیل کو ضرورت سے پہلے شمار کیا جاتا ہے، اور نئی غیر موثر آپریشن کو کال کرنے سے پہلے نئی فرنٹ لسٹ کو مکمل طور پر شمار کیا جاتا ہے۔ مستقل ڈیٹا ڈھانچہ بھی دیکھیں حوالہ جات بیرونی روابط خالص فنکشنل ڈیٹا ڈھانچے کا مقالہ کرس اوکاساکی (پی ڈی ایف فارمیٹ) ڈیٹا ڈھانچے کو مستقل بنانا جیمز آر ڈریسکول، نیل سرنک، ڈینیل ڈی سلیٹر، رابرٹ ای ٹارجن (پی ڈی ایف) جیمز آر ڈریسکول، ڈینیل ڈی سلیٹر، رابرٹ ای ٹارجن (پی ڈی ایف) کیٹی نیشن کے ساتھ مکمل مستقل فہرستیں ایم آئی ٹی اوپن کورس ویئر کورس سے مستقل ڈیٹا ڈھانچے اعلی درجے کے الگورتھم اوکاساکی کے بعد سے خالص فعال ڈیٹا ڈھانچے میں کیا نیا ہے؟ نظریاتی کمپیوٹر سائنس اسٹیک ایکسچینج فنکشنل ڈیٹا ڈھانچے فنکشنل پروگرامنگ پر