I wish they would stop calling those data structures functional. Just call them immutable. It's the other way around. Functional languages use immutable data structures. One can use those "functional"data structures with any programming paradigma (not sure how to use them in Prolog though).
Calling them "persistent data structures" is probably more useful.
Prolog has "difference lists", which are (currently) pretty unique to Prolog. Its special case of variables that can be mutated, but only once, has interesting implications.
Okasaki called them that because he was implementing data structures in pure functional languages, so in that context it was reasonable. But in imperative languages, you're right, calling them "purely functional" is meaningless.
