Calculate edit distances and edit scripts between vectors.


Version on this page:
LTS Haskell 19.7:
Stackage Nightly 2022-05-14:
Latest on Hackage:

See all snapshots edit-distance-vector appears in

BSD-3-Clause licensed by Thomas Sutton
This version can be pinned in stack with:edit-distance-vector-,1676

Module documentation for

Depends on 2 packages(full list with versions):
Used by 1 package in nightly-2015-12-04(full list with versions):

Edit Distance: Vector

Build Status

This is a small library for calculating the edit distance and edit script between two vectors. It is generic enough that you should be able to use it with vectors containing values of any type you like, with changes described by any type you like, and with costs represented by any type you like (with a few restrictions).


The edit-distance-vector package is a normal Haskell library and can be installed using the Cabal package management tool.

cabal update
cabal install edit-distance-vector

edit-distance-vector is automatically tested on GHC versions 7.4.2, 7.6.3, 7.8.3, and 7.10.1 using the Travis CI service.


The interface to edit-distance-vector is very small; just import Data.Vector.Distance, create a Params value with the correct operations to deal with your types, and pass this to leastChanges along with your Vectors.

import qualified Data.Vector as V
import           Data.Vector.Distance

-- | Editing vectors of 'Char' values, with '(String, Int, Char)' describing
--   changes, and the additive monoid of 'Int' describing costs.
str :: Params Char (String, Int, Char) (Sum Int)
str = Params
    { equivalent = (==)
    , delete i c = ("delete", i, c)
    , insert i c = ("insert", i, c)
    , substitute i c c' = ("replace", i, c')
    , cost _ = 1
    , positionOffset (op,_,_) | op == "delete" = 0
                              | otherwise      = 1

main :: IO ()
main = do
    print $ leastChanges str (V.fromList "I am thomas")
                             (V.fromList "My name is Thomas")



* Relax version bounds to support GHC 7.6.3 and 7.4.2


* Relax version bounds to support GHC 7.10.1.

edit-distance-vector 1.0

* Initial release extracted from aeson-diff package and rewritten to use