Purely functional data structure: Difference between revisions

Revision as of 00:57, 13 November 2018

Revision as of 15:32, 2 December 2018

Line 6:

==Definition==

Purely[[Persistent functionaldata structure|Persistent data structures]] arehave oftenthe representedproperty inof akeeping differentprevious wayversions thanof theirthemselves unmodified. On the other hand, structures such as [[imperativeArray programmingdata structure|imperativearrays]] counterparts.admit '''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>, Forthat exampleis, an arrayupdate which can not be replacedcancelled. byOnce a [[Mapprogram (computer science)|map]],writes a random access list, or a tree, which admits a purely functional implementation, but access and update operations may runvalue in [[logarithmicsome time]].index [[Persistent data structure|Persistent data structures]] haveof the property of keeping previous versions of themselves unmodifiedarray, andits areprecedent usedvalue ascan functionalnot alternativesbe toretrieved theiranymore. imperative counterparts.

Formally a ''Purely functional data structure'' is a data structure which can be implemented in a [[purely functional language]], such as [[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, all persistent data structures are not purely functional {{r|Okasaki-book|16}}. For exemples a [[persistent array]] is a data-structure which is persistent and which is implemented using an array, thus which is not purely functional.

In the book ''Purely functional data structures, Okasaki compare destructive updates to master chef's knives{{r|Okasaki-book|2}}. Destructive updates can not 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 tree, which admits a purely functional implementation. But the access cost may increase from constant time to to [[logarithmic time]].

==Ensuring that a data structure is purely functional==