Content deleted Content added
Seriousman9 (talk | contribs) →Amortized analysis and scheduling: I made what I believe to be a small edit on this topic, by reference to the page on the real-time queue (https://en.wikipedia.org/wiki/Queue_(abstract_data_type)#Real-time_queue). However, it did reverse the meaning of a part of the article, and I am only now learning about these things. |
→Definition: (m) clarify |
||
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}}
| |||