Content deleted Content added
Adding local short description: "Data structure implementable in purely functional languages", overriding Wikidata description "persistent data structure that does not rely on mutable state" |
→Definition: (m) clarify |
||
| (One intermediate revision by one other user not shown) | |||
Line 5:
==Definition==
[[Persistent data structure]]s have the property of keeping previous versions of themselves unmodified. On the other 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> that is, an update which cannot be reversed. Once a program writes a value in some index of the array, its previous value can not be retrieved anymore.{{citation needed|date=December 2018}}
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}}
Line 50:
====Example: queue====
[[Amortized queue]]s{{r|Okasaki-book|p=65}}{{r|Okasaki-book|p=73}} are composed of two singly-linked lists: 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
==See also==
| |||