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. — 象嘉道, Oct 21 '12 at 00:52

score 3 · Answer 1 · answered Oct 21 '12 at 00:58

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.

score 1 · Answer 2 · answered Oct 21 '12 at 00:51

1

You would write a function to build a NEW list (in this case, one with the new element added to the old list) & return that.

answered Oct 21 '12 at 00:51

Scott Hunter

48,888
12
60
101

4

+1. Most functional languages use a list structure where adding to one end (usually the head) is trivial. Note that if you can't modify anything, there's no need to make a copy of the rest, deep or otherwise. Multiple lists can share the same sublist. – Mark Reed Oct 21 '12 at 00:55

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

2 Answers2

Linked