Чисто функционални програмски језик
У рачунарству, алгоритми, структуре података или програмски језици се називају чисто функционални ако гарантују (слаб) еквивалентност call-by-name, call-by-value и call-by-need стратегија евалуације, често без деструктивне модификације (исправке) ентитета у програмском систему извршавања.[1] Према овом ограничењу, променљиве се користе у математичком смислу, са идентификаторима који се односе на непроменљиве, перзистентне вредности.
За представљање израчунавања које обављају споредне ефекте у чистом функционалном програмском језику, могу се користити монаде, као што је предложио Филип Вадлер.[2]
Haskell је један од најпознатијих савремених примера чистог функционалног програмског језика.
Чисте функционалне структуре података се често представљају на другачији начин него њихови императивни партнери.[3]
Предности и апликације уреди
Истрајно својство чисто функционалне структуре података може да буде предност у развоју многих апликација којим се баве више верзија једног објекта.
На пример, размотримо свеобухватне веб-основне речнике услуга који користе велико црвено-црно дрво за складиштење својих листа синонима односа, а који омогућавају сваком кориснику да додају своје сопствене прилагођене речи у свој лични речник. Један од начина да то урадите је да направите копију дрвета за сваког корисника, а затим додајте своје прилагођене речи на њега; међутим, ово копирање се расипа, у простору и времену.
Бољи приступ је да сачувате речи у непроменљивом (и стога чисто функционалне) црвено-црном дрвету. Затим, једноставно можете да узмете оригиналну верзију и направите ново основно дрво за сваки скуп царинских речи. Због овог ново дрвеће дели велике количине структура са главним дрветом, простор изнад главе за сваког додатног корисника је највише 2klog2n, где је к број царинских чворова. Са једном променљивом црвено-црног стабла, овај приступ не би функционисао, јер промене у главном стаблу утичу на све кориснике.
Поред својих ефикасних предности, својствена референтна транспарентност функционалних структура података тежи да потпуно функционално прорачуна више подложних анализа и оптимизација, и формално и неформално.
Види још уреди
Референце уреди
- ^ Sabry, Amr (1998). „What is a purely functional language?”. Journal of Functional Progrmaming. 8 (1): 1—22.
- ^ Comprehending Monads by Philip Wadler, Cambridge University Press, Mathematical Structures in Computer Science / Volume 2 / Issue 04 / December (1992). стр. 461-493
- ^ Purely functional data structures by Chris Okasaki, Cambridge University Press. 1998. ISBN 978-0-521-66350-2.
Спољашње везе уреди
- Purely Functional Data Structures thesis by Chris Okasaki (PDF format)
- Making Data-Structures Persistent by James R. Driscoll, Neil Sarnak, Daniel D. Sleator, Robert E. Tarjan (PDF)
- Fully Persistent Lists with Catenation by James R. Driscoll, Daniel D. Sleator, Robert E. Tarjan (PDF)
- Persistent Data Structures from MIT open course Advanced Algorithms