Purely functional

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.

Contents

1 Examples of purely functional data structures 1.1 Linked lists 1.2 Trees 2 Notes 3 Bibliography

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.

Consider the two lists:

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

These would be represented in memory by:

Missing image
Purely_functional_list_before.gif
image:purely_functional_list_before.gif

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:

Missing image
Purely_functional_list_after.gif
image:purely_functional_list_after.gif

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.

For instance, the set of data

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

might be represented by the following binary search tree:

Missing image
Purely_functional_tree_before.gif
Image:purely_functional_tree_before.gif

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:

Missing image
Purely_functional_tree_after.gif
Image:purely_functional_tree_after.gif

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.

Notes

Such persistence can be advantageous in the development of many applications. Moreover, the inherent referential transparency tends to make purely functional computation more amenable to analysis, both formal and informal.

Since every value in an purely functional computation is built up out of existing values, it would seem that it were impossible to create a cycle of references, resulting in an reference graph (a graph which has edges from objects to the objects they reference) that is a directed acyclic graph. However, this is not true. Even under eager evaluation, functions can be defined recursively, referring to themselves. And under lazy evaluation, even regular data structures can be defined self-referentially.

Bibliography

Purely functional data structures by Chris Okasaki, Cambridge University Press, 1998, ISBN 0-521-66350-4.