-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Calculate edit distances and edit scripts between vectors.
--
@package edit-distance-vector
@version 1.0
-- | This module implements a variation on the Wagner-Fischer
-- algorithm to find the shortest sequences of operations which
-- transforms one vector of values into another.
module Data.Vector.Distance
-- | Operations invoked by the Wagner-Fischer algorithm.
--
-- The parameters to this type are as follows:
--
--
-- - v is the type of values being compared,
-- - o is the type representing operations,
-- - c is the type representing costs.
--
--
-- The chief restrictions on these type parameters is that the cost type
-- c must have instances of Monoid and Ord. A good
-- default choice might be the type (Sum Int).
data Params v o c
Params :: (v -> v -> Bool) -> (Int -> v -> o) -> (Int -> v -> o) -> (Int -> v -> v -> o) -> (o -> c) -> (o -> Int) -> Params v o c
-- | Are two values equivalent?
equivalent :: Params v o c -> v -> v -> Bool
-- | Delete the element at an index.
delete :: Params v o c -> Int -> v -> o
-- | Insert an element at an index.
insert :: Params v o c -> Int -> v -> o
-- | Substitute an element at an index.
substitute :: Params v o c -> Int -> v -> v -> o
-- | Cost of a change.
cost :: Params v o c -> o -> c
-- | Positions to advance after a change. E.g. 0 for a deletion.
positionOffset :: Params v o c -> o -> Int
-- | Matrix of optimal edit scripts and costs for all prefixes of two
-- vectors.
--
-- This is a representation of the n * m dynamic programming
-- matrix constructed by the algorithm. The matrix is stored in a
-- Vector in row-major format with an additional row and column
-- corresponding to the empty prefix of the source and destination
-- Vectors.
type ChangeMatrix o c = Vector (c, [o])
-- | O(nm). Find the cost and optimal edit script to transform one
-- Vector into another.
leastChanges :: (Monoid c, Ord c) => Params v o c -> Vector v -> Vector v -> (c, [o])
-- | O(nm). Calculate the complete matrix of edit scripts and costs
-- between two vectors.
allChanges :: (Monoid c, Ord c) => Params v o c -> Vector v -> Vector v -> ChangeMatrix o c
-- | Example Params to compare (Vector Char)
-- values.
--
-- The algorithm will produce edit distances in terms of (Sum
-- Int) and edit scripts containing (String, Int,
-- Char) values.
--
-- The first component of each operation is either "delete",
-- "insert", or "replace".
strParams :: Params Char (String, Int, Char) (Sum Int)