Purely functional data structure: Difference between revisions

Revision as of 09:32, 3 December 2018

Revision as of 21:57, 13 December 2018

Line 8:

[[Persistent data structure|Persistent data structures]] have the property of keeping previous versions of themselves unmodified. On the other hand, structures such as [[Array data structure|arrays]] 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>, that is, an update which can not be cancelled. Once a program writes a value in some index of the array, its precedent 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, all persistent data structures are not purely functional {{r|Okasaki-book|p=16}}. For exemplesexample, a [[persistent array]] is a data-structure which is persistent and which is implemented using an array, thus which is not purely functional.{{cn|date=December 2018}}

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

==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, the run-time system may be unable to guarantee immutability. This is illustrated by Okasaki{{r|Okasaki-book|pp=9-11}}, where he shows the the catenation of two singly-linked list can still be done using an imperative setting.{{cn|date=December 2018}}

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.{{cn|date=December 2018}}