Although pure functional programming can express many abstractions cleanly and succinctly, certain algoithms are better written imperatively. These algorithms require mutation to be efficient and/or more concise. In response, functional languages have developed techniques for delimiting where mutation can occur while still permitting results to be communicated between pure and impure portions of a program. To maintain purity, however, these techniques typically prevent data structures created impurely from escaping into pure portions, severely impeding the construction of complex objects. The standard workaround relies on the builder pattern. Unfortunately, this approach incurs runtime overhead and leads to code duplication.

In this talk, we present a technique for encoding objects and data structures in a language with subtyping and singleton types so that they are mutable any way you want it only where you want it. The essence of our idea is to only allow mutation on an object where the corresponding capability object is present, which we enforce using singleton types reminiscent to how Launchbury and Jones [1994] enforce purity using rank-2 polymorphic types. As a result, one can notionally “take away” the part of an object’s API that causes mutation by rescinding the capability, thus allowing in-place construction without dedicated builders. We have implemented our technique in Scala with only minimal changes to its compiler, thereby showing that our encoding is lightweight and interoperable with existing impure programs.