I mean there's a whole book about this, "Purely Functional Data Structures" (2009) by Chris Okasaki.