gap/myers

Types

pub type Edit(a) {
  Eq(List(a))
  Del(List(a))
  Ins(List(a))
}

</>

pub fn difference(
  list1: List(a),
  list2: List(a),
) -> List(Edit(a))

The algorithm is outlined in the “An O(ND) Difference Algorithm and Its Variations” paper by E. Myers.

Adapted from the implementation of “myers_difference” in Elixirs List module