As functional programmers we always face a dilemma: should we write purely
functional code, or sacrifice purity for efficiency and resort to in-place
updates? This paper identifies precisely when we can have the best of both
worlds: a wide class of purely functional programs can be executed safely using
in-place updates without requiring allocation, provided their arguments are not
shared elsewhere.

We describe a linear fully in-place (FIP) calculus where we prove that we can
always execute such functions in a way that requires no (de)allocation and uses
constant stack space. Of course, such a calculus is only relevant if we can
express interesting algorithms; we provide numerous examples of in-place
functions on datastructures such as splay trees or finger trees, together with
in-place versions of merge sort and quick sort.

We also show how we can generically derive a map function over any polynomial
data type that is fully in-place. Finally, we have implemented the rules of the
FIP calculus in the Koka language. Using the Perceus reference counting garbage
collection, this implementation dynamically executes FIP functions in-place
whenever possible.