This is an implementation of the O(ND) diff algorithm as described in "An O(ND) Difference Algorithm and Its Variations (1986)" http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.6927. It is O(mn) in space. The algorithm is the same one used by standared Unix diff.
A value is either from the
First list, the
Second or from
Both contains both the left and right values, in case you are using a form
of equality that doesn't check all data (for example, if you are using a
newtype to only perform equality on side of a tuple).