Purely functional

Purely functional

Purely functional is a term in computing used to describe algorithms, data structures or programming languages that exclude destructive modifications (updates). According to this restriction, variables are used in a mathematical sense, with identifiers referring to immutable, persistent values.

Contents

Benefits and applications

The persistence property of purely functional data structures can be advantageous in the development of many applications which deal with multiple versions of an object.

For example, consider a comprehensive web-based thesaurus service that uses a large red-black tree to store its list of synonym relationships, and that allows each user to add their own custom words to their personal thesaurus. One way to do this is to make a copy of the tree for each user, and then add their custom words to it; however, this duplication is wasteful, both of space and of time.

A better approach is to store the words in an immutable (and therefore purely functional) red-black tree. Then, one can simply take the original version and produce a new tree based on it for each set of custom words. Because these new trees share large amounts of structure with the main tree, the space overhead for each additional user is at most 2klog 2n, where k is the number of custom nodes. With a mutable red-black tree, this approach would not work, since changes to the main tree would affect all users.

Besides their efficiency benefits, the inherent referential transparency of functional data structures tends to make purely functional computation more amenable to analysis and optimization, both formal and informal.

See also

Bibliography

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Functional programming — In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast with the… …   Wikipedia

  • functional — func|tion|al [ fʌŋkʃənl ] adjective ** 1. ) designed to be good at doing a particular job: These traditional tools are both functional and attractive. highly functional: the highly functional arrangement of the control panel a ) practical and… …   Usage of the words and phrases in modern English

  • functional */*/ — UK [ˈfʌŋkʃ(ə)nəl] / US [ˈfʌŋkʃən(ə)l] adjective 1) a) designed to be good at doing a particular job These traditional tools are both functional and attractive. highly functional: the highly functional arrangement of the control panel b) practical …   English dictionary

  • functional — func|tion|al [ˈfʌŋkʃənəl] adj 1.) designed to be useful rather than beautiful or attractive ≠ ↑decorative ▪ buildings that are sensitively designed, not purely functional 2.) something that is functional is working correctly = ↑operational ▪ By… …   Dictionary of contemporary English

  • Functional decomposition — refers broadly to the process of resolving a functional relationship into its constituent parts in such a way that the original function can be reconstructed (i.e., recomposed) from those parts by function composition. In general, this process of …   Wikipedia

  • Functional theories of grammar — A range of functionally based approaches to the scientific study of language have been termed functional . The grammar model developed by Simon Dik bears this qualification in its name, Functional Grammar, as does Michael Halliday s Systemic… …   Wikipedia

  • Monad (functional programming) — In functional programming, a monad is a programming structure that represents computations. Monads are a kind of abstract data type constructor that encapsulate program logic instead of data in the domain model. A defined monad allows the… …   Wikipedia

  • List of functional programming topics — This is a list of functional programming topics. Contents 1 Foundational concepts 2 Lambda calculus 3 Combinatory logic 4 Intuitionistic logic …   Wikipedia

  • Holomorphic functional calculus — In mathematics, holomorphic functional calculus is functional calculus with holomorphic functions. That is to say, given a holomorphic function fnof; of a complex argument z and an operator T , the aim is to construct an operator:f(T),which in a… …   Wikipedia

  • Borel functional calculus — In functional analysis, a branch of mathematics, the Borel functional calculus is a functional calculus (that is, an assignment of operators from commutative algebras to functions defined on their spectrum), which has particularly broad… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”