In practice the two terms do seem to be almost synonymous, as functional data structures have to be persistent, and so efficient functional data structures have

In practice the two terms do seem to be almost synonymous, as functional data structures have to be persistent, and so efficient functional data structures have to be efficiently persistent. But it's possible for a persistent data structure not to be purely functional. Here's a realistic example. A trie can be updated functionally, as this article describes. However, when the trie is initially being constructed, so that there is known to be only one variable holding a pointer to the root, it is unnecessary to use functional update to add each node (which would generate a lot of garbage). The nodes can be added by side-effect, and then once the trie's initial state is complete and its root pointer is exposed for use by the rest of the program, subsequent updates can then be done functionally.