"Copying" an immutable singly-linked list is just copying the reference to the first element. That is, the entire list is really shared, not actually copied element by element like an array would have to be. But since it is immutable, this doesn't matter: You cannot change it in a way that would mess up other users' view of the list.

What you can still do is cons new elements to the front of your copy. No other copy of the list will be affected. Because the list is singly linked, other owners of references into the list cannot walk back to observe your elements. They can even cons their new elements to the "same" list without any conflict.

All this is very useful if you want to process something with a stack, such that sub-operations can push elements to the stack that they have to remove again before returning. Pushing x and y to the stack is just constructing the list y : x : stack. Popping y and x from the stack when you're done is a no-op: "stack" is still a reference to the stack as it was before these operations.

Hum... Okay, rereading it all, I see the parent meant an immutable use of a singly linked list? I hadn't clued in on that the first time around.

I'd still have to say that Singly Linked List arn't ideal for that either, better use a persistent hash array mapped trie backed list instead.

> better use a persistent hash array mapped trie backed list instead

there's a real memory overhead for that structure.

If it's immutable there's no need to copy.

That's true of any data-structure though.