-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Calculate edit distances and edit scripts between vectors.
--   
--   An implementation of the Wagner–Fischer dynamic programming algorithm
--   to find the optimal edit script and cost between two sequences.
--   
--   The implementation in this package is specialised to sequences
--   represented with <a>Data.Vector</a> but is otherwise agnostic to:
--   
--   <ul>
--   <li>The type of values in the vectors;</li>
--   <li>The type representing edit operations; and</li>
--   <li>The type representing the cost of operations.</li>
--   </ul>
@package edit-distance-vector
@version 1.0.0.4


-- | This module implements a variation on the <a>Wagner-Fischer</a>
--   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:
--   
--   <ul>
--   <li><tt>v</tt> is the type of values being compared,</li>
--   <li><tt>o</tt> is the type representing operations,</li>
--   <li><tt>c</tt> is the type representing costs.</li>
--   </ul>
--   
--   The chief restrictions on these type parameters is that the cost type
--   <tt>c</tt> must have instances of <a>Monoid</a> and <a>Ord</a>. A good
--   default choice might be the type <tt>(<a>Sum</a> <a>Int</a>)</tt>.
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. <tt>0</tt> 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 <tt>n * m</tt> dynamic programming
--   matrix constructed by the algorithm. The matrix is stored in a
--   <a>Vector</a> in row-major format with an additional row and column
--   corresponding to the empty prefix of the source and destination
--   <tt>Vectors</tt>.
type ChangeMatrix o c = Vector (c, [o])

-- | <i>O(nm).</i> Find the cost and optimal edit script to transform one
--   <a>Vector</a> into another.
leastChanges :: (Monoid c, Ord c) => Params v o c -> Vector v -> Vector v -> (c, [o])

-- | <i>O(nm).</i> 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 <a>Params</a> to compare <tt>(<a>Vector</a> <a>Char</a>)</tt>
--   values.
--   
--   The algorithm will produce edit distances in terms of <tt>(<a>Sum</a>
--   <a>Int</a>)</tt> and edit scripts containing <tt>(String, Int,
--   Char)</tt> values.
--   
--   The first component of each operation is either <tt>"delete"</tt>,
--   <tt>"insert"</tt>, or <tt>"replace"</tt>.
strParams :: Params Char (String, Int, Char) (Sum Int)
