Type-Directed Diffing of Structured Data

Abstract

The Unix diff utility that compares lines of text is used pervasively by version control systems. Yet certain changes to a program may be dicult to describe accurately in terms of modications to individual lines of code. As a result, observing changes at such a xed granularity may lead to unnecessary conicts between dierent edits. This paper presents a generic representation for describing transformations between algebraic data types and a non-deterministic algorithm for computing such representations. These representations can be used to give a more accurate account of modications made to algebraic data structures – and the abstract syntax trees of computer programs in particular – as opposed to only considering modications between their textual representations.