Purely functional is a term in computing used to describe algorithms, data structures or programming languages that exclude destructive modifications (updates). As a consequence of this restriction, variables refer to immutable, persistent values. This means that old values available prior to a change continue to be accessible and may be updated following a modification. Originally, the word computing was synonymous with counting and calculating, and a science that deals with the original sense of computing mathematical calculations. ... Flowcharts are often used to represent algorithms. ... A binary tree, a simple type of branching linked data structure. ... Computer code (HTML with JavaScript) in a tool that uses syntax highlighting (colors) to help the developer see the purpose of each piece of code. ...

Examples of purely functional data structures

Linked lists

This example is taken from Okasaki. See the bibliography.

Singly linked lists 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. In computer science, a linked list is one of the fundamental data structures used in computer programming. ... ML is a general-purpose functional programming language developed by Robin Milner and others in the late 1970s at the University of Edinburgh, whose syntax is inspired by ISWIM. Historically, ML stands for metalanguage as it was conceived to develop proof tactics in the LCF theorem prover (the language of... Haskell is a standardized pure functional programming language with non-strict semantics named after the logician Haskell Curry. ...

Consider the two lists:

 xs = [0, 1, 2] ys = [3, 4, 5] 

These would be represented in memory by:

Image File history File links Purely_functional_list_before. ...

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:

Image File history File links Purely_functional_list_after. ...

Notice that the nodes in list xs have been copied, but the nodes in ys are shared. As a result, the original lists (xs and ys) persist and have not been modified.

The reason for the copy is that the last node in xs (the node containing the original value 2) cannot be 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. In computer science, a binary tree is a tree data structure in which each node has at most two children. ... A Sierpinski triangle —a confined recursion of triangles to form a geometric lattice. ... In computer science, optimising compilers and the methodology of design by contract pay close attention to invariant quantities in computer programs, where the set of transformations involved is the execution of the steps of the computer program. ...

For instance, the set of data

 xs = [a, b, c, d, f, g, h] 

might be represented by the following binary search tree:

Image File history File links Purely_functional_tree_before. ...

A function which inserts data into the binary tree and maintains the invariant is:

 fun insert (x, E) = T (E, x, E) | insert (x, s as T (a, y, b)) = if x < y then T (insert (x, a), y, b) else if x > y then T (a, y, insert (x, b)) else s 

After executing

 ys = insert ("e", xs) 

we end up with the following:

Image File history File links Purely_functional_tree_after. ...

Notice two points: Firstly the original tree (xs) persists. Secondly many common nodes are shared between the old tree and the new tree. Such persistence and sharing is difficult to manage without some form of garbage collection (GC) to automatically free up nodes which have no live references, and this is why GC is a feature commonly found in functional programming languages. In computer science, garbage collection (also known as GC) is a form of automatic memory management. ...

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 red-black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. ...

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 2klog₂ n or about 40k 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. In computer programming, a referentially transparent function is one that, given the same parameter(s), always returns the same result. ...

Reference cycles

Since every value in a purely functional computation is built up out of existing values, it would seem that it is impossible to create a cycle of references, resulting in a reference graph (a graph which has edges from objects to the objects they reference) that is a directed acyclic graph. However, in most functional languages, functions can be defined recursively; this capability allows recursive structures using functional suspensions. In lazy languages, such as Haskell, all data structures are explicitly suspended; in these languages any data structure can be recursive. Some other languages, such as Objective Caml, allow the explicit definition of recursive values. A simple directed acyclic graph In computer science and mathematics, a directed acyclic graph, also called a dag or DAG, is a directed graph with no directed cycles; that is, for any vertex v, there is no nonempty directed path starting and ending on v. ... A Sierpinski triangle —a confined recursion of triangles to form a geometric lattice. ... In computer programming, lazy evaluation is a technique that attempts to delay computation of expressions until the results of the computation are known to be needed. ... Haskell is a standardized pure functional programming language with non-strict semantics named after the logician Haskell Curry. ... Objective Caml, also known as OCaml or OCaml for short, is an advanced programming language that is part of the ML family. ...

Bibliography

Purely functional data structures by Chris Okasaki, Cambridge University Press, 1998, ISBN 0-521-66350-4. The headquarters of the Cambridge University Press, in Trumpington Street, Cambridge. ... 1998 (MCMXCVIII) was a common year starting on Thursday of the Gregorian calendar, and was designated the International Year of the Ocean. ...