pure functional programming: how to add an element to a list?

Question

In pure functional programming, we do not modify any arguments of a function. Then, how can we design a function that adds an element to its argument, a list? For example, function list add (elem, list). This question is similar to this thread: Functional programming: state vs. reassignment .

My guess solution is to deep-copy the input list and then to use some destructive operations like append to manipulate the new one. Am I right?

appending

I copy the following code from a graph-copy algorithm:

// in Node
public Node deepCopy(Map<Node, Node> isomorphism) {
    Node copy = isomorphism.get(this);
    if (copy == null) {
        copy = new Node();
        isomorphism.put(this, copy);
        for (Node connection: connections) {
            copy.connections.add(connection.deepCopy(isomorphism));
        }
    }
    return copy;
}

To deep-copy a graph, one must track every node that is being copied. In the universe, we use the isomorphism argument to do that. I think the only way to make a pure functional version of this deepCopy operation is to return not only the variable copy but also a flag indicating whether the returned node is new one. Right?

@hammar That's what I actually concerned: such new object creation operations may be very expensive. — 象嘉道

hammar hammar · Accepted Answer · 2012-10-21T00:58:23

Yes, you have to return a new list with the element added.

However, this doesn't have to require a deep copy. Functional languages typically feature persistent data structures which allow parts of the structure to be shared between versions, so that you can e.g. prepend an element to a list in O(1) time.

pure functional programming: how to add an element to a list?

2 Answers