A library for patches (diffs) on vectors: composable, mergeable and invertible
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.


https://travis-ci.org/liamoc/patches-vector.svg https://img.shields.io/hackage/v/patches-vector.svg https://img.shields.io/hackage-deps/v/patches-vector.svg https://img.shields.io/badge/language-Haskell-blue.svg http://img.shields.io/badge/license-BSD3-brightgreen.svg

Patches for Vectors

A patch is a collection of modifications (edits) to be made to a sequence of elements. Commonly found in version control systems, patches are also a simple example of a groupoid, supporting (partial) composition and inversion.

This library provides a pleasant interface for working with patches to vectors with any type of element. It includes patch composition, inversion, and application, as well as a way to compute a patch between two vectors using the Wagner-Fischer algorithm.

It also includes a simple implementation of the operational transformation (OT) function to resolve diverging patches from the same document. This allows for reasonably painless implementation of merge functions, as well as many applications in distributed editing of documents. This operation also has an interpretation in terms of groupoids, where the transform function is the pushout of two diverging patches.

This library is extensively covered by a comprehensive suite of QuickCheck properties, which are written into the documentation and run with doctest.

The actual package only depends on base, microlens, vector and a small library for doing Wagner-Fischer, thsutton/edit-distance-vector.

It is released under the BSD3 license.

Building, Installing

patches-vector is released on Hackage and is available in the usual way:

$ cabal update
$ cabal install patches-vector

You can also use stack if you prefer:

$ stack install patches-vector

A variety of stack-*.yaml files are provided in this repository for various LTS snapshots.


The full Haddock documentation is available on Hackage. Mostly, construct patches using fromList or diff, compose them with the Monoid instance, invert them with inverse, and apply them to a vector with apply.

The transform function can be used to resolve diverging patches, and transformWith lets you select a merging strategy, such as ours or theirs, rather than the default mappend. See the Haddock documentation for more information.

The hunks function can be used with a patch and a vector to provide a list of change hunks, that are convenient for other tools or for displaying to the user.

Future work

  • More elaborate merge strategies that allow you to emulate insert/delete style patches.

Other notes

This library is designed to be used with my composition-tree library, which, along with this library gives you a basic version control system for vectors. Pretty neat!