You can build ephemeral data structures in functional languages, and persistent data structures in imperative languages. (It's just not their default idiom.)

The ease and simplicity of the book's implementations owes to pattern matching syntax more than anything else.

As an aside: pattern matching on algebraic datatypes is awesome, and just like other innovations before, like garbage collection and first-class closures, I hope to see it transplanted to more and more mainstream languages.