Purely functional data structure
કોમ્પ્યુટર વિજ્ઞાનમાં, શુદ્ધ કાર્યાત્મક માહિતી માળખું એ માહિતી માળખું છે જે સીધી રીતે શુદ્ધ કાર્યાત્મક ભાષામાં લાગુ કરી શકાય છે. મનસ્વી માહિતી માળખું અને શુદ્ધ કાર્યાત્મક માળખું વચ્ચેનો મુખ્ય તફાવત એ છે કે પછીનું (મજબૂત રીતે) અપરિવર્તનીય છે. આ પ્રતિબંધ એ સુનિશ્ચિત કરે છે કે માહિતી માળખું અપરિવર્તનીય પદાર્થોના ફાયદા ધરાવે છેઃ (સંપૂર્ણ) સ્થિરતા, પદાર્થોની ઝડપી નકલ અને થ્રેડ સલામતી. કાર્યક્ષમ શુદ્ધ કાર્યાત્મક ડેટા સ્ટ્રક્ચર્સને આળસુ મૂલ્યાંકન અને મેમોઇઝેશનના ઉપયોગની જરૂર પડી શકે છે. વ્યાખ્યા સતત ડેટા સ્ટ્રક્ચર્સ પાસે પોતાની અગાઉની આવૃત્તિઓને બિનપરિવર્તિત રાખવાનો ગુણધર્મ છે. બીજી બાજુ, એરે જેવી રચનાઓ વિનાશક અપડેટને સ્વીકારે છે, એટલે કે, એક અપડેટ જેને ઉલટાવી શકાતું નથી. એકવાર પ્રોગ્રામ એરેના અમુક અનુક્રમણિકામાં મૂલ્ય લખે, પછી તેનું અગાઉનું મૂલ્ય હવે પુનઃપ્રાપ્ત કરી શકાતું નથી. ઔપચારિક રીતે, શુદ્ધ કાર્યાત્મક માહિતી માળખું એ માહિતી માળખું છે જે હાસ્કેલ જેવી શુદ્ધ કાર્યાત્મક ભાષામાં લાગુ કરી શકાય છે. વ્યવહારમાં, તેનો અર્થ એ છે કે ડેટા સ્ટ્રક્ચર્સ માત્ર ટુપલ્સ, સમ પ્રકારો, ઉત્પાદન પ્રકારો અને પૂર્ણાંકો, અક્ષરો, શબ્દમાળાઓ જેવા મૂળભૂત પ્રકારો જેવા સતત ડેટા સ્ટ્રક્ચર્સનો ઉપયોગ કરીને બનાવવામાં આવવી જોઈએ. આવી માહિતી માળખું આવશ્યકપણે સતત રહે છે. જો કે, તમામ સ્થાયી ડેટા સ્ટ્રક્ચર્સ સંપૂર્ણપણે કાર્યરત નથી. ઉદાહરણ તરીકે, પર્સિસ્ટન્ટ એરે એ ડેટા-સ્ટ્રક્ચર છે જે પર્સિસ્ટન્ટ છે અને જે એરેનો ઉપયોગ કરીને અમલમાં મૂકવામાં આવે છે, તેથી તે સંપૂર્ણપણે કાર્યાત્મક નથી. પુસ્તક પ્યોરલી ફંક્શનલ ડેટા સ્ટ્રક્ચર્સમાં, ઓકાસાકી વિનાશક સુધારાઓની તુલના માસ્ટર શેફની છરીઓ સાથે કરે છે. વિનાશક સુધારાઓને પૂર્વવત્ કરી શકાતા નથી, અને તેથી તેનો ઉપયોગ ત્યાં સુધી થવો જોઈએ નહીં જ્યાં સુધી તે ચોક્કસ ન હોય કે અગાઉના મૂલ્યની હવે જરૂર નથી. જો કે, વિનાશક સુધારાઓ કાર્યક્ષમતાને પણ મંજૂરી આપી શકે છે જે અન્ય તકનીકોનો ઉપયોગ કરીને મેળવી શકાતી નથી. ઉદાહરણ તરીકે, એરે અને વિનાશક સુધારાઓનો ઉપયોગ કરતા ડેટા માળખાને સમાન ડેટા માળખા દ્વારા બદલી શકાય છે જ્યાં એરેને નકશા, રેન્ડમ એક્સેસ સૂચિ અથવા સંતુલિત વૃક્ષ દ્વારા બદલવામાં આવે છે, જે સંપૂર્ણપણે કાર્યાત્મક અમલીકરણને સ્વીકારે છે. પરંતુ પ્રવેશ ખર્ચ સતત સમયથી લઘુગણક સમય સુધી વધી શકે છે. માહિતી માળખું સંપૂર્ણપણે કાર્યાત્મક છે તેની ખાતરી કરવી એ માહિતી માળખું ક્યારેય સ્વાભાવિક રીતે કાર્યાત્મક હોતું નથી. ઉદાહરણ તરીકે, સ્ટેકને સિંગલ-લિન્ક્ડ સૂચિ તરીકે લાગુ કરી શકાય છે. આ અમલીકરણ સંપૂર્ણપણે કાર્યરત છે જ્યાં સુધી સ્ટૅક પરની એકમાત્ર કામગીરી જૂના સ્ટેકને બદલ્યા વિના નવા સ્ટેકને પરત કરે છે. જો કે, જો ભાષા સંપૂર્ણપણે કાર્યરત ન હોય, તો રન-ટાઇમ સિસ્ટમ અપરિવર્તનીયતાની બાંયધરી આપવામાં અસમર્થ હોઈ શકે છે. આ ઓકાસાકી દ્વારા સચિત્ર છે, જ્યાં તે બતાવે છે કે બે એકલ-જોડાયેલી સૂચિઓનું સંયોજન હજુ પણ અનિવાર્ય સેટિંગનો ઉપયોગ કરીને કરી શકાય છે. ડેટા સ્ટ્રક્ચરનો ઉપયોગ શુદ્ધ કાર્યાત્મક રીતે અશુદ્ધ કાર્યાત્મક ભાષામાં થાય છે તેની ખાતરી કરવા માટે, મોડ્યુલો અથવા વર્ગોનો ઉપયોગ માત્ર અધિકૃત કાર્યો દ્વારા હેરફેરની ખાતરી કરવા માટે કરી શકાય છે. શુદ્ધ કાર્યાત્મક ડેટા સ્ટ્રક્ચર્સનો ઉપયોગ કરવો એ શુદ્ધ કાર્યાત્મક ડેટા સ્ટ્રક્ચર્સનો ઉપયોગ કરવા માટે હાલના કોડને સ્વીકારવામાં એક કેન્દ્રીય પડકાર એ હકીકતમાં રહેલો છે કે પરિવર્તનીય ડેટા સ્ટ્રક્ચર્સ તેનો ઉપયોગ કરતા કાર્યો માટે "છુપાયેલા આઉટપુટ" પ્રદાન કરે છે. શુદ્ધ કાર્યાત્મક ડેટા સ્ટ્રક્ચર્સનો ઉપયોગ કરવા માટે આ કાર્યોને ફરીથી લખવા માટે આ ડેટા સ્ટ્રક્ચર્સને સ્પષ્ટ આઉટપુટ તરીકે ઉમેરવાની જરૂર છે. દાખલા તરીકે, એવા કાર્યને ધ્યાનમાં લો જે પરિવર્તનીય સૂચિને સ્વીકારે છે, સૂચિમાંથી પ્રથમ તત્વને દૂર કરે છે અને તે તત્વને પરત કરે છે. શુદ્ધ કાર્યાત્મક સેટિંગમાં, સૂચિમાંથી કોઈ તત્વને દૂર કરવાથી નવી અને ટૂંકી સૂચિ ઉત્પન્ન થાય છે, પરંતુ મૂળ સૂચિને અપડેટ કરતું નથી. ઉપયોગી બનવા માટે, તેથી, આ કાર્યના શુદ્ધ કાર્યાત્મક સંસ્કરણને દૂર કરેલા ઘટક સાથે નવી સૂચિ પરત કરવાની શક્યતા છે. સૌથી સામાન્ય કિસ્સામાં, આ રીતે રૂપાંતરિત પ્રોગ્રામે દરેક ફંક્શન કોલના વધારાના પરિણામ તરીકે પ્રોગ્રામની "સ્થિતિ" અથવા "સ્ટોર" પરત કરવી આવશ્યક છે. આવા કાર્યક્રમ સ્ટોર-પાસિંગ શૈલીમાં લખાયેલા હોવાનું કહેવાય છે. ઉદાહરણો અહીં શુદ્ધ કાર્યાત્મક અમલીકરણ સાથે અમૂર્ત ડેટા સ્ટ્રક્ચર્સની સૂચિ છેઃ એકલ રીતે જોડાયેલી સૂચિ તરીકે અમલમાં મૂકાયેલ સ્ટૅક (પ્રથમ ઇન, છેલ્લું આઉટ), કતાર, વાસ્તવિક સમયની કતાર તરીકે અમલમાં મૂકાયેલ, ડબલ-એન્ડેડ કતાર, વાસ્તવિક સમયની ડબલ-એન્ડેડ કતાર તરીકે અમલમાં મૂકાયેલ, (મલ્ટી) આદેશિત તત્વોનો સમૂહ અને આદેશિત કીઓ દ્વારા અનુક્રમિત નકશો, લાલ-કાળા વૃક્ષ તરીકે અમલમાં મૂકાયેલ, અથવા વધુ સામાન્ય રીતે સર્ચ ટ્રી દ્વારા, પ્રાથમિકતા કતાર, બ્રોડલ કતાર રેન્ડમ એક્સેસ સૂચિ તરીકે અમલમાં મૂકાયેલ, સ્ક્યુ-દ્વિસંગી રેન્ડમ એક્સેસ સૂચિ તરીકે અમલમાં મૂકાયેલ, હેશિંગ ઝિપર (ડેટા સ્ટ્રક્ચર) ડિઝાઇન અને અમલીકરણ તેમના પુસ્તક પ્યોરલી ફંક્શનલ ડેટા સ્ટ્રક્ચર્સમાં, કમ્પ્યુટર વૈજ્ઞાનિક ક્રિસ ઓકાસાકી શુદ્ધ કાર્યાત્મક ડિઝાઇન અને અમલીકરણ માટે ઉપયોગમાં લેવાતી તકનીકોનું વર્ણન કરે છે. આળસ અને યાદગીરી આળસુ મૂલ્યાંકન શુદ્ધ કાર્યાત્મક ભાષામાં ખાસ કરીને રસપ્રદ છે કારણ કે મૂલ્યાંકનનો ક્રમ કાર્યના પરિણામને ક્યારેય બદલતો નથી. તેથી, આળસુ મૂલ્યાંકન સ્વાભાવિક રીતે શુદ્ધ કાર્યાત્મક ડેટા સ્ટ્રક્ચર્સના નિર્માણનો એક મહત્વપૂર્ણ ભાગ બની જાય છે. તે ગણતરી ત્યારે જ કરવાની મંજૂરી આપે છે જ્યારે તેનું પરિણામ ખરેખર જરૂરી હોય. તેથી, શુદ્ધ કાર્યાત્મક ડેટા સ્ટ્રક્ચરનો કોડ, કાર્યક્ષમતામાં ઘટાડો કર્યા વિના, તે જ રીતે ડેટાનો વિચાર કરી શકે છે જેનો અસરકારક રીતે ઉપયોગ કરવામાં આવશે અને ડેટાને અવગણવામાં આવશે. એકમાત્ર ગણતરી પ્રથમ પ્રકારની માહિતી માટે જરૂરી છે; તે જ ખરેખર કરવામાં આવશે. કાર્યક્ષમ, સંપૂર્ણપણે કાર્યાત્મક ડેટા સ્ટ્રક્ચર્સના નિર્માણમાં મુખ્ય સાધનોમાંથી એક મેમોઇઝેશન છે. જ્યારે ગણતરી કરવામાં આવે છે, ત્યારે તે સાચવવામાં આવે છે અને બીજી વખત કરવાની જરૂર નથી. આળસુ અમલીકરણમાં આ ખાસ કરીને મહત્વનું છે; વધારાના મૂલ્યાંકન માટે સમાન પરિણામની જરૂર પડી શકે છે, પરંતુ તે જાણવું અશક્ય છે કે કયા મૂલ્યાંકન માટે તેને પહેલા જરૂર પડશે. કેટલાક ડેટા સ્ટ્રક્ચર્સ, જેમ કે ડાયનેમિક એરે, એવા ઓપરેશનને સ્વીકારે છે જે મોટાભાગે કાર્યક્ષમ હોય છે (દા. ત., ડાયનેમિક એરે માટે સતત સમય), અને ભાગ્યે જ બિનકાર્યક્ષમ (દા. ત., ડાયનેમિક એરે માટે રેખીય સમય). પછી અમોર્ટાઇઝેશનનો ઉપયોગ એ સાબિત કરવા માટે કરી શકાય છે કે કામગીરીનો સરેરાશ ચાલતો સમય કાર્યક્ષમ છે. એટલે કે, કેટલીક બિનકાર્યક્ષમ કામગીરીઓ દુર્લભ છે, અને જ્યારે કામગીરીના ક્રમને ધ્યાનમાં લેવામાં આવે ત્યારે સમયની જટિલતાના એસિમ્પ્ટોટિકલ ઉત્ક્રાંતિમાં ફેરફાર થતો નથી. સામાન્ય રીતે, સતત ડેટા સ્ટ્રક્ચર્સ માટે બિનકાર્યક્ષમ કામગીરી સ્વીકાર્ય નથી, કારણ કે આ જ કામગીરીને ઘણી વખત કહી શકાય. તે વાસ્તવિક સમય માટે અથવા અનિવાર્ય પ્રણાલીઓ માટે સ્વીકાર્ય નથી, જ્યાં વપરાશકર્તાને કામગીરી દ્વારા લેવામાં આવેલા સમયની આગાહી કરવાની જરૂર પડી શકે છે. વધુમાં, આ અનિશ્ચિતતા સમાંતરતાના ઉપયોગને જટિલ બનાવે છે. તે સમસ્યાઓને ટાળવા માટે, કેટલાક ડેટા સ્ટ્રક્ચર્સ બિનકાર્યક્ષમ કામગીરીને મુલતવી રાખવાની મંજૂરી આપે છે-આને શેડ્યૂલિંગ કહેવામાં આવે છે. એકમાત્ર જરૂરિયાત એ છે કે બિનકાર્યક્ષમ કામગીરીની ગણતરી તેના પરિણામની ખરેખર જરૂર પડે તે પહેલાં સમાપ્ત થવી જોઈએ. બિનકાર્યક્ષમ કામગીરીનો સતત ભાગ કાર્યક્ષમ કામગીરી માટે નીચેના કોલ સાથે એક સાથે કરવામાં આવે છે, જેથી જ્યારે જરૂર પડે ત્યારે બિનકાર્યક્ષમ કામગીરી પહેલેથી જ સંપૂર્ણપણે થઈ જાય અને દરેક વ્યક્તિગત કામગીરી કાર્યક્ષમ રહે. ઉદાહરણ તરીકેઃ કતાર અમોર્ટાઇઝ્ડ કતારો બે સિંગલ-લિન્ક્ડ યાદીઓથી બનેલી છેઃ ફ્રન્ટ અને રિવર્સ રીઅર. તત્વોને પાછળની સૂચિમાં ઉમેરવામાં આવે છે અને આગળની સૂચિમાંથી દૂર કરવામાં આવે છે. વધુમાં, જ્યારે પણ આગળની કતાર ખાલી હોય છે, ત્યારે પાછળની કતાર ઉલટાવી દેવામાં આવે છે અને આગળની બની જાય છે, જ્યારે પાછળની કતાર ખાલી થઈ જાય છે. દરેક કામગીરીની ઋણમુક્ત સમયની જટિલતા સતત રહે છે. સૂચિના દરેક કોષને વધુમાં વધુ એક વાર ઉમેરવામાં આવે છે, ઉલટાવી દેવામાં આવે છે અને દૂર કરવામાં આવે છે. જ્યાં પાછળની સૂચિ ઉલટાવી દેવામાં આવે છે તે બિનકાર્યક્ષમ કામગીરીને ટાળવા માટે, વાસ્તવિક સમયની કતારો પ્રતિબંધ ઉમેરે છે કે પાછળની સૂચિ માત્ર આગળની સૂચિ જેટલી લાંબી છે. પાછળની સૂચિ આગળની સૂચિ કરતાં લાંબી બને તે સુનિશ્ચિત કરવા માટે, આગળની સૂચિને પાછળની સૂચિમાં જોડવામાં આવે છે અને ઉલટાવી દેવામાં આવે છે. આ ઓપરેશન બિનકાર્યક્ષમ હોવાથી, તે તરત જ કરવામાં આવતું નથી. તેના બદલે, તે પછીની કામગીરીઓમાં ફેલાયેલું છે. આમ, દરેક કોષની ગણતરી તેની જરૂર પડે તે પહેલાં કરવામાં આવે છે, અને નવી બિનકાર્યક્ષમ કામગીરીની જરૂર પડે તે પહેલાં નવી આગળની સૂચિ સંપૂર્ણપણે ગણવામાં આવે છે. પર્સિસ્ટન્ટ ડેટા સ્ટ્રક્ચર સંદર્ભો ક્રિસ ઓકાસાકી દ્વારા બાહ્ય કડીઓ શુદ્ધ કાર્યાત્મક ડેટા સ્ટ્રક્ચર્સ થીસીસ (પીડીએફ ફોર્મેટ) જેમ્સ આર. ડ્રિસ્કોલ, નીલ સારનાક, ડેનિયલ ડી. સ્લેટર, રોબર્ટ ઇ. ટાર્જન દ્વારા ડેટા-સ્ટ્રક્ચર્સને સતત બનાવવું (પીડીએફ) જેમ્સ આર. ડ્રિસ્કોલ, ડેનિયલ ડી. સ્લેટર, રોબર્ટ ઇ. ટાર્જન (પીડીએફ) દ્વારા કેટેનેશન સાથે સંપૂર્ણ પર્સિસ્ટન્ટ લિસ્ટ્સ એમઆઇટી ઓપનકોર્સવેર કોર્સમાંથી પર્સિસ્ટન્ટ ડેટા સ્ટ્રક્ચર્સ એડવાન્સ્ડ અલ્ગોરિધમ્સ ઓકાસાકીથી શુદ્ધ કાર્યાત્મક ડેટા સ્ટ્રક્ચર્સમાં શું નવું છે? સૈદ્ધાંતિક કોમ્પ્યુટર સાયન્સ સ્ટેક એક્સચેન્જ પર કાર્યાત્મક ડેટા સ્ટ્રક્ચર્સ કાર્યાત્મક પ્રોગ્રામિંગ