Purely functional data structure: Difference between revisions

Revision as of 14:08, 23 September 2017

Latest revision as of 19:47, 2 April 2024

(39 intermediate revisions by 25 users not shown)

Line 1:

{{Short description|Data structure implementable in purely functional languages}}

{{multiple issues|

{{copymore editcitations needed|date=January 2017}}

{{expert needed|date=January 2017}}

{{refimprove|date=January 2017}}}}

In [[computer science]], a '''purely functional data structure''' is a [[data structure]] that can be directly implemented in a [[purely functional language]]. The main difference between an arbitrary data structure and a purely functional one is that athe purely functional data structurelatter is (strongly) [[immutable object|immutable]]. This restriction ensures the modemdata hasstructure everypossesses advantagethe overadvantages of immutable objects: (full) [[persistent data structure|persistency]],<nowiki/> quick copy of objects, and [[thread safety]]. Efficient purely functional data structures may require the use of [[lazy evaluation]] and [[memorizationmemoization]].{{not typo}}

==Definition==

Purely functional[[Persistent data structuresstructure]]s arehave oftenthe representedproperty inof akeeping differentprevious wayversions thanof theirthemselves unmodified. On the stdother counterparts.hand, non-persistent structures such as [[Array data structure|arrays]] admit a '''destructive update''',<ref name="Okasaki-book">[http://www.cambridge.org/us/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/purely-functional-data-structures ''Purely functional data structures''] by [[Chris Okasaki]], [[Cambridge University Press]], 1998, {{ISBN|0-521-66350-4}}</ref> Forthat exampleis, an [[array data structure|array]] with constant-time access and update iswhich acannot basic component of most imperativebe languagesreversed. Many imperative data structures, such as the [[hash table]] and [[binary heap]], are based on arrays. An array can be replaced byOnce a [[Map (computer science)|map]] or random access list, whichprogram admitswrites a purely functional implementation, but access and update operations may runvalue in [[logarithmicsome time]].index Purelyof functionalthe data structures can be implemented in imperative and object-oriented languagesarray, butits theirprevious timevalue and/or space performancecan maynot be inferiorretrieved to that of data structures lacking purely functional propertiesanymore.{{cncitation needed|date=JulyDecember 20172018}}

Formally, a ''purely functional data structure'' is a data structure which can be implemented in a [[purely functional language]], such as [[Haskell (programming language)|Haskell]]. In practice, it means that the data structures must be built using only persistent data structures such as tuples, [[sum type]]s, [[product type]]s, and basic types such as integers, characters, strings. Such a data structure is necessarily persistent. However, not all persistent data structures are purely functional.{{r|Okasaki-book|p=16}} For example, a [[persistent array]] is a data-structure which is persistent and which is implemented using an array, thus is not purely functional.{{citation needed|date=December 2018}}

In the book ''Purely functional data structures'', Okasaki compares destructive updates to master chef's knives.{{r|Okasaki-book|p=2}} Destructive updates cannot be undone, and thus they should not be used unless it is certain that the previous value is not required anymore. However, destructive updates can also allow efficiency that can not be obtained using other techniques. For example, a data structure using an array and destructive updates may be replaced by a similar data structure where the array is replaced by a [[Map (computer science)|map]], a random access list, or a [[balanced tree]], which admits a purely functional implementation. But the access cost may increase from constant time to [[logarithmic time]].{{citation needed|date=December 2018}}

==Ensuring that a data structure is purely functional==

A data structure is never inherently functional. For example, a stack can be implemented as a [[singly-linked list]]. This implementation is purely functional as long as the only operations on the stack return a new stack without altering the old stack. However, if the language is not [[purely functional language|purely functional]], the run-time system may be unable to guarantee immutability. This is illustrated by Okasaki,{{r|Okasaki-book|pp=9-11}} where he shows the concatenation of two singly-linked lists can still be done using an imperative setting.{{citation needed|date=December 2018}}

In order to ensure that a data structure is used in a purely functional way in an impure functional language, [[modular programming|modules]] or [[class (computer programming)|classes]] can be used to ensure manipulation via authorized functions only.{{citation needed|date=December 2018}}

==Using purely functional data structures==

One of the central challenges in adapting existing code to use purely functional data structures lies in the fact that mutable data

structures provide "hidden outputs" for functions that use them. Rewriting these functions to use purely functional data structures

requires adding these data structures as explicit outputs.

For instance, consider a function that accepts a mutable list, removes the first element from the list, and returns that element. In a purely functional setting, removing an element from the list produces a new and shorter list, but does not update the original one. In order to be useful, therefore, a purely functional version of this function is likely to have to return the new list along with the removed element. In the most general case, a program converted in this way must return the "state" or "store" of the program as an additional result from every function call. Such a program is said to be written in [[store-passing style]].

In order to ensure that a data structure is used in a purely functional way in an impure functional language, [[modular programming|modules]] or [[class (computer programming)|classes]] can be used to ensure manipulation via authorized functions only.

==Examples==

Here is a list of an abstract data structurestructures with a purely functional implementationimplementations:

* Stack (first in, last out) implemented as a [[singly linked list]],

* Queue, implemented as a [[real-time queue]],

* Double-ended queue, implemented as a [[real-time deque|real-time double-ended queue]],

* [[Set (abstract data type)|(Multi)set]] of ordered elements and [[map (computer science)|map]] indexed by ordered keys, implemented as a [[red–black tree]], or more generally by a [[search tree]],

* [[Priority queue]], implemented as a [[Brodal queue]]

* Random access list, implemented as a skew-binary random access list

* [[Hash consing]]

* [[Zipper (data structure)]]

==Design and implementation==

In his book ''Purely Functional Data Structures'', computer scientist [[Chris Okasaki]] describes techniques used to design and implement purely functional data structures, a small subset of which are summarized below.

===Laziness and memoization===

[[Lazy evaluation]] is particularly interesting in a purely functional language{{r|Okasaki-book|p=31}} because the order of the evaluation never changes the result of a function. Therefore, lazy evaluation naturally becomes an important part of the construction of purely functional data structures. It allows a computation to be done only when its result is actually required. Therefore, the code of a purely functional data structure can, without loss of efficiency, consider similarsimilarly data whichthat will effectively be used and data whichthat will be ignored. The only computation required is for the first kind of data; that is what will actually be performed.{{citation needed|date=December 2018}}

One of the key tools in building efficient, purely functional data structures is [[memoization]].{{r|Okasaki-book|p=31}} When a computation is done, it is saved and does not have to be performed a second time. This is particularly important in lazy implementations; additional evaluations may require the same result, but it is impossible to know which evaluation will require it first.{{citation Thereneeded|date=December are actually many books that pertain to purely functional data structures that can give you a more in-depth sight of laziness and memorization.2018}}

===Amortized analysis and scheduling===

Some data structures, even non-those that are not purely- functional ones such as [[dynamic array|dynamic arrays]]s, admit operationoperations whichthat isare efficient most of the time (e.g., constant time for dynamic arrays) most of the time, and rarely inefficient (e.g., linear time for dynamic arrays) rarely. ''[[Amortized analysis|Amortization]]'' can then be used to prove that the average running time of the operations is efficient.{{r|Okasaki-book|p=39}} That is to say, the few inefficient operations are rare enough, and doesdo not change the asymptotical evolution of the time complexity when a sequence of operations is considered.{{citation needed|date=December 2018}}

In general, having inefficient operations is not acceptable for persistent data structures, because this inefficientvery operation can be called many times. It is not acceptable either for real-time or for imperative systems, where the user may require the time taken by the operation to be predictable. Furthermore, this unpredictability complicates the use of [[Parallel computing|parallelism]].{{r|Okasaki-book|p=83}}{{citation needed|date=December 2018}}

In order to avoid those problems, some data structures allow for the inefficient operation to be postponed, thispostponed—this is called ''[[Scheduling (computing)|scheduling'']].{{r|Okasaki-book|p=84}} The only requirement is that the computation of the inefficient operation endsshould end before theits result of the operation is actually needed. A constant part of the inefficient operation is performed simultaneously with the following call to an efficient operation, so that, the inefficient operation is already totally done when it is needed, and each individual operationsoperation remains efficient.{{clarify|date=September 2017}}

====Example: queue====

For example, [[amortizedAmortized queue]]s{{r|Okasaki-book|p=65}}{{r|Okasaki-book|p=73}} are composed of two [[singly -linked list]]slists: the front and the reversed rear. Elements are added to the rear list and are removed from the frontlistfront list. Furthermore, each time thatwhenever the front queue is empty, the rear queue is reversed and becomes the front queue, while the rear queue becomes empty. The amortized time complexity of each operation is constant. Each cell of the list is added, reversed and removed at most once. In order to avoid thean inefficient operation where the rear list is reversed, [[real-time queue]]s, addsadd the restriction that the rear list is only as long as the frontlistfront list. To ensure that the rearfront list becomesstays longer than the frontlistrear list, the frontlistrear list is appendedreversed and reversedappended to the rearfront list. Since this operation is inefficient, it is not performed immediately. Instead, it is performedspread forout eachover ofthe thesubsequent operations. ThereforeThus, each cell is computed before it is needed, and the new frontlistfront list is totally computed before the moment when a new inefficient operation needs to be called.{{citation needed|date=December 2018}}

==See Bibliography also==

* [[Persistent data structure]]

==References==

{{reflist}}

==External links==

*[httphttps://www.cs.cmu.edu/~rwh/thesesstudents/okasaki.pdf Purely Functional Data Structures] thesis by Chris Okasaki (PDF format)

*[httphttps://www.cs.cmu.edu/~sleator/papers/making-data-structures-persistent.pdf Making Data-Structures Persistent] by James R. Driscoll, Neil Sarnak, Daniel D. Sleator, Robert E. Tarjan (PDF)

*[httphttps://www.cs.cmu.edu/~sleator/papers/fully-persistent-lists.pdf Fully Persistent Lists with Catenation] by James R. Driscoll, Daniel D. Sleator, Robert E. Tarjan (PDF)

Mitchell Crossland is the best (SMD)

*[http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2005/lecture-notes/persistent.pdf Persistent Data Structures] from the [[MIT OpenCourseWare]] course [http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2005 Advanced Algorithms]

*[httphttps://cstheory.stackexchange.com/questionsq/1539/whats-new-in-purely-functional-data-structures-since-okasaki What's new in purely functional data structures since OkazakiOkasaki?] on [http://cstheory.stackexchange.com/ ''Theoretical Computer Science StackExchange[[Stack Exchange]]''

[[Category:Functional programming]]

[[Category:Functional data structures]]

[[Category:Functional programming]]