Data.Diff

First-divergence reporting for two lists.

A differential check answers one question: are these two sequences the same, and if not, where do they first stop being the same? Equality alone answers the first half and throws away the second, which is the half a failure message is made of. This module keeps both: the answer is None when the lists agree everywhere, and otherwise the one index where they first part company plus what each side holds there.

Divergence has exactly three shapes, because two lists walked in lockstep can only part in three ways: both sides have an element at the index and the elements differ, or one side ran out while the other continued. A shorter list is therefore never reported as a difference at some element, and the index in every shape means the same thing, the number of positions that agreed before it.

The scan stops at the first divergence, so comparing two long lists that part early costs the agreeing prefix and nothing more.

match first_diff([1, 2, 3], [1, 9, 3]) of
  None => println("equal")
  Some(d) => println(diff_message(d))

index 1: left 2, right 9

Opt-in: not in Base.

Types

Divergence

type Divergence(a)
  = DiffAt(Int, a, a)
  | DiffLeftEnd(Int, a)
  | DiffRightEnd(Int, a)
  deriving (Eq, Show)

Where and how two lists first differ. DiffAt(i, left, right) is a genuine element mismatch at index i; DiffLeftEnd(i, right) is the left list ending at i while the right still holds an element there; DiffRightEnd(i, left) is the mirror image.

Functions and Values

first_diff

first_diff : forall a. (List(a), List(a)) -> Option(Data.Diff.Divergence(a)) given Eq(a)

Where xs and ys first differ, or None when they are equal. The elements are compared with their own Eq, so this agrees with == on the whole lists exactly.

(first_diff([1, 2], [1, 2]), first_diff([1, 2, 3], [1, 2]))

(None, Some(Data.Diff.DiffRightEnd(2, 3)))

first_diff_by

first_diff_by : forall e0 a. ((a, a) -> Bool ! {e0}, List(a), List(a)) -> Option(Data.Diff.Divergence(a)) ! {e0}

Where xs and ys first differ under the caller’s notion of sameness. same(x, y) decides whether two elements count as agreeing, which is what a comparison that ignores part of an element (a span, a cached size) needs.

first_diff_by(\(x, y) -> x % 10 == y % 10, [11, 22], [1, 5])

Some(Data.Diff.DiffAt(1, 22, 5))

diff_index

diff_index : forall a. (Data.Diff.Divergence(a)) -> Int

The index a divergence sits at: the number of positions that agreed before the two lists parted. The three shapes all count the same way, so a caller reporting a position never matches on the shape first.

(diff_index(DiffAt(1, 2, 9)), diff_index(DiffLeftEnd(3, 4)))

(1, 3)

diff_message

diff_message : forall a. (Data.Diff.Divergence(a)) -> String given Show(a)

One line naming the divergence, for a failure message. The constructor’s own Show renders the shape; this renders the story.

diff_message(DiffLeftEnd(2, 7))

index 2: left ended, right 7