Purely functional data structure: Difference between revisions

Revision as of 20:33, 30 September 2017

Revision as of 20:40, 30 September 2017

Line 1:

{{goceinuse}}

{{multiple issues|

{{copy edit|date=January 2017}}

{{expert needed|date=January 2017}}

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

Line 11 ⟶ 9:

==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.

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.

Line 29 ⟶ 27:

===Laziness and memoization===

[[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 computations 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 that will effectively be used and data that 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.

===Amortized analysis and scheduling===

Line 41 ⟶ 39:

====Example: queue====

[[Amortized queue]]s 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 front list. Furthermore, whenever the front queue is empty, the rear queue is reversed and becomes the front, 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 an inefficient operation where the rear list is reversed, [[real-time queue]]s add the restriction that the rear list is only as long as the front list. To ensure that the rear list becomes longer than the front list, the front list is appended to the rear list and reversed. Since this operation is inefficient, it is not performed immediately. Instead, it is carried out for each of the operations. Thus, each cell is computed before it is needed, and the new front list is totally computed before a new inefficient operation needs to be called.

== Bibliography ==