Purely functional data structure: Difference between revisions

Revision as of 21:03, 12 September 2017

Revision as of 21:26, 20 September 2017

Line 4:

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

In [[computer science]], a '''purely functional data structure''' is a [[data structure]] that can be implemented in a [[purely functional language]]. The main difference between an arbitrary data structure and a purely functional one is that a purely functional data structure is (strongly) [[immutable object|immutable]]. This restriction ensures the data structure possesses the advantages 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 [[memoizationmemorization]].

==Definition==

Line 30:

[[Lazy evaluation]] is particularly interesting in a purely functional language 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 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 similar data which will effectively be used and data which will be ignored. The only computation required is for the first kind of data that will actually be performed.

One of the key tools in building efficient, purely functional data structures is [[memoization]]. 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. There are actually many books that pertain to purely functional data structures that can give you a more in -depth sight of laziness and memoizationmemorization.

===Amortized analysis and scheduling===

Some data structures, even non-purely-functional ones such as [[dynamic array|dynamic arrays]], admit operation which is efficient (constant time for dynamic arrays) most of the time, and inefficient (linear time for dynamic arrays) rarely. ''[[Amortized analysis|Amortization]]'' can then be used to prove that the average running time of the operations areis efficient. That is, the few inefficient operations are rare enough, and does not change the asymptotical evolution of the time complexity when a sequence of operations is considered.

In general, having inefficient operations is not acceptable for persistent data structures, because this inefficient operation can be called many times. It is not acceptable either for real-time or 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]].

Line 40:

====Example: queue====

For example, [[amortized queue]]s are composed of two [[singly linked list]]s: the front and the reversed rear. Elements are added to the rear list and are removed from the front listfrontlist. Furthermore, each time that 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 the inefficient operation where the rear list is reversed, [[real-time queue]]s, adds the restriction that the rear list is only as long as the front listfrontlist. To ensure that the rear list becomes longer than the front listfrontlist, the front listfrontlist is appended and reversed to the rear list. Since this operation is inefficient, it is not performed immediately. Instead, it is performed for each of the operations. Therefore, each cell is computed before it is needed, and the new front listfrontlist is totally computed before the moment when a new inefficient operation needs to be called.

== Bibliography ==

Line 50:

*[http://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)

*[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]

*[http://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki What's new in purely functional data structures since Okasaki?Okazaki] on [http://cstheory.stackexchange.com/ Theoretical Computer Science StackExchange]

[[Category:Functional programming]]