| Purely Functional |
Website Links For Functional |
Information AboutPurely Functional |
| CATEGORIES ABOUT PURELY FUNCTIONAL | |
| functional programming | |
|
''Purely functional'' is a term in Computing used to describe Algorithm s, Data Structure s or Programming Language s that exclude destructive modifications (updates). According to this restriction, variables are not used, with identifiers instead referring to immutable, persistent values. 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, say you have a thesaurus service on a website which uses a Red-black Tree to store its list of which words are synonyms for which other words. Because your thesaurus is comprehensive, this tree has about a million nodes. Now say you wish to add a feature that allows each user of your site 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, but this is wasteful, because each user using the service simultaneously would require memory for at least a million nodes. Moreover, it would cause a significant processing delay to make the complete copy of the tree. A better approach is to store the words in a purely functional red-black tree. Then, you 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''log2 ''n'' or about 40''k'' nodes, where ''k'' is the number of custom nodes. 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. EXAMPLES OF PURELY FUNCTIONAL DATA STRUCTURES Linked lists This example is taken from Okasaki. See the bibliography. Singly Linked List s are a bread and butter data structure in functional languages. In ML -derived languages and Haskell , they are purely functional because once a node in the list has been allocated, it cannot be modified, only copied or destroyed. Consider the two lists: xs = 1, 2 ys = 4, 5 These would be represented in memory by: where a circle indicates a node in the list (the arrow out showing the second element of the node which is a pointer to another node). Now concatenating the two lists: zs = xs ++ ys results in the following memory structure: Notice that the nodes in list xs havebeen copied, but the nodes in ys areshared. As a result, the original lists ( xsand ys) persist and have not been modified.The reason for the copy is that the last node in xs (the node containingthe original value 2) cannotbe modified to point to the start of ys,because that would change the value of xs.Trees This example is taken from Okasaki. See the bibliography. Consider a Binary Tree used for fast searching, where every node has the Recursive Invariant that subnodes on the left are less than the node, and subnodes on the right are greater than the node. For instance, the set of data xs = b, c, d, f, g, h might be represented by the following binary search tree: A function which inserts data into the binary tree and maintains the invariant is: fun insert (x, E) = T (E, x, E) |
|
|