There's a whole book of these if you're interested:

Purely Functional Data Structures by Chris Okasaki