Purely functional

From Wikipedia, the free encyclopedia
  (Redirected from Pure functional language)
Jump to: navigation, search

In computing, algorithms, data structures, or programming languages are called purely functional if they guarantee the (weak) equivalence of call-by-name, call-by-value and call-by-need evaluation strategies, often by excluding destructive modifications (updates) of entities in the program's running environment.[1] According to this restriction, variables are used in a mathematical sense, with identifiers referring to immutable, persistent values.

To represent computations that perform side-effects in a purely functional programming language, one can use Monads, as proposed by Philip Wadler.[2]

Haskell is the most common modern example of a purported pure functional programming language; however the mutable reference feature of its IO monad effectively renders it impure.[3]

Purely functional data structures are often represented in a different way than their imperative counterparts.[4]

Benefits and applications[edit]

The persistence property of purely functional data structures can be advantageous in the development of many applications that 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 2 k \log_2 n, where k is the number of custom nodes. With a single 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[edit]

Bibliography[edit]

  1. ^ Sabry, Amr (January 1998). "What is a purely functional language?". Journal of Functional Progrmaming 8 (1): 1–22. 
  2. ^ Comprehending Monads by Philip Wadler, Cambridge University Press, Mathematical Structures in Computer Science / Volume 2 / Issue 04 / December 1992, pp 461-493
  3. ^ A Functional Approach to the Observer Pattern by Alvaro Garcia Perez
  4. ^ Purely functional data structures by Chris Okasaki, Cambridge University Press, 1998, ISBN 0-521-66350-4

External links[edit]