Content deleted Content added
Adding WikiProject-based category (using WikiProjects listed on talk page) as parameter to {{expert needed}} template, to clear out the completely unhelpful Category:Articles needing unspecified expert attention. |
→Definition: Fix misplaced "not" Tags: Mobile edit Mobile app edit Android app edit |
||
Line 8:
[[Persistent data structure]]s have the property of keeping previous versions of themselves unmodified. On the other hand, 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.{{cn|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
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]].{{cn|date=December 2018}}
| |||