We present patch and diff functions that are generic over families of datatypes. The edit scripts are represented as values in a type-indexed datatype, and both computing and applying edit scripts is entirely type-safe. Our approach extends classic string diff and tree diff algorithms by providing more informative types. We have working implementations in Agda and Haskell.
Andres Löh, 2009-12-18