Data structures in Haskell are persistent useless you use ST-refs or similar. Coupled with sharing this can bring some optimizations, e.g. here: http://www.haskell.org/pipermail/haskell-cafe/2009-May/061368.html Admittedly the efficiencies in that message are on somewhat trivial use-cases. Best wishes Stephen