Breaking the complexity barrier of pure functional programs with impure data structures
Pieter Wuille, Tom Schrijvers · Lirias · 2008
Abstract. Pure functional programming language offer many advan-tages over impure languages. Unfortunately, the absence of destructive update, imposes a complexity barrier. In imperative languages, there are algorithms and data structures with better complexity. We present our project for combining existing program transformation techniques to transform inefficient pure data structures into impure ones with better complexity. As a consequence, the programmer is not exposed to the impurity and retains the advantages of purity. 1