Well luckily, Haskell is full of said "specialized structures."

containers and unordered-containers handle most of your needs and they only copy their trees' spines (O log n) on update.