Are purely functional data structures always lock-free?

Question

I've seen this claimed in several places, including on SO: https://stackoverflow.com/a/20467457/243238, https://stackoverflow.com/a/4400389/243238. I get the point that locks are not needed to modify the data but you end up with multiple versions of it after concurrent modifications. That doesn't seem very useful in practice. I've tried to describe this with a simple scenario below:

Let's say we have 2 threads A and B. They are both modifying a purely functional dictionary D. They don't need locks at this point because the data is immutable so they output new dictionaries DA and DB. Now my question is how do you reconcile DA and DB so that later operations can see a single view of the data?

EDIT: The answers are suggesting to use a merge function over DA and DB. I don't see how that solves the problem since there could be another thread C which runs concurrently with the merge operation. The claim is that purely functional data structures are lock-free but using a merge function sounds more like eventual consistency which is a different thing.

Answer 1

Good observation. But this just means that parallelism in the presence of a "global state" is difficult or impossible, regardless of the programming language.

In impure languages, this is just less obvious. You may think that you can get away with locking, synchronization and all the highly complex code around it.

Whereas in pure languages, you have n pure state transformers and cannot but realize that if you apply them in pareallel to some initial state S0 you end up with so many states S1, S2, S3 ... Sn

Now, the purity just guarantees that the parallel transformations of S0 do not interfere with each other in any way. It doesn't solve your program design issues, such as what that state means, if it is maybe too coarse, or too fine grained and if you can compute an end result form various transformed states.