Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Purely functional data structure
Summary
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. This restriction ensures the data structure possesses the advantages of immutable objects: (full) persistency, quick copy of objects, and thread safety. Efficient purely functional data structures may require the use of lazy evaluation and memoization.
Persistent data structures have the property of keeping previous versions of themselves unmodified. On the other hand, structures such as arrays admit a destructive update, 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.
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 types, product types, and basic types such as integers, characters, strings. Such a data structure is necessarily persistent. However, not all persistent data structures are purely functional. For example, a persistent array is a data-structure which is persistent and which is implemented using an array, thus is not purely functional.
In the book Purely functional data structures, Okasaki compares destructive updates to master chef's knives. 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, a random access list, or a balanced tree, which admits a purely functional implementation.
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.