Purely functional data structure: Difference between revisions

Revision as of 21:27, 18 January 2022

Latest revision as of 19:47, 2 April 2024

(6 intermediate revisions by 5 users not shown)

Line 1:

{{Short description|Data structure implementable in purely functional languages}}

{{more citations needed|date=January 2017}}

In [[computer science]], a '''purely functional data structure''' is a [[data structure]] that can be directly implemented in a [[purely functional language]]. The main difference between an arbitrary data structure and a purely functional one is that the latter is (strongly) [[immutable object|immutable]]. This restriction ensures the data structure possesses the advantages of immutable objects: (full) [[persistent data structure|persistency]],<nowiki/> quick copy of objects, and [[thread safety]]. Efficient purely functional data structures may require the use of [[lazy evaluation]] and [[memoization]].{{not typo}}

==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 15 ⟶ 16:

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

==Using Purelypurely Functionalfunctional Datadata Structuresstructures==

One of the central challenges in adapting existing code to use purely functional data structures lies in the fact that mutable data

structures provide "hidden outputs" for functions that use them. Rewriting these functions to use purely functional data structures

requires adding these data structures as explicit outputs.

For instance, consider a function that accepts a mutable list, insertsremoves anthe first element intofrom the list, and returns thethat length of the new listelement. In a purely functional setting, insertingremoving a newan element intofrom the list produces a new and shorter list, but does not update the original one. In order to be useful, therefore, a purely functional version of this function is likely to have to return both the lengthnew oflist thealong list andwith the newremoved list itselfelement. In the most general case, a program converted in this way must return the "state" or "store" of the program as an additional result from every function call. Such a program is said to be written in [[store-passing style]].

==Examples==

Line 49 ⟶ 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 rearfront list becomesstays longer than the frontrear list, the frontrear list is reversed and appended to the rearfront list and reversed. Since this operation is inefficient, it is not performed immediately. Instead, it is spread out over the subsequent operations. Thus, each cell is computed before it is needed, and the new front list is totally computed before a new inefficient operation needs to be called.{{citation needed|date=December 2018}}

==See also==

Line 59 ⟶ 60:

==External links==

*[https://www.cs.cmu.edu/~rwh/thesesstudents/okasaki.pdf Purely Functional Data Structures] thesis by Chris Okasaki (PDF format)

*[https://www.cs.cmu.edu/~sleator/papers/making-data-structures-persistent.pdf Making Data-Structures Persistent] by James R. Driscoll, Neil Sarnak, Daniel D. Sleator, Robert E. Tarjan (PDF)

*[https://www.cs.cmu.edu/~sleator/papers/fully-persistent-lists.pdf Fully Persistent Lists with Catenation] by James R. Driscoll, Daniel D. Sleator, Robert E. Tarjan (PDF)