You can consult Okasaki's thesis (regrettably it is somewhat out of date) for a list of functional data structures. Some of them are lazy, some of them are strict. But being able to use all them is essential to getting good asymptotic complexity.