Safe Haskell  None 

Language  Haskell2010 
This module implements a variation on the WagnerFischer algorithm to find the shortest sequences of operations which transforms one vector of values into another.
 data Params v o c = Params {
 equivalent :: v > v > Bool
 delete :: Int > v > o
 insert :: Int > v > o
 substitute :: Int > v > v > o
 cost :: o > c
 positionOffset :: o > Int
 type ChangeMatrix o c = Vector (c, [o])
 leastChanges :: (Monoid c, Ord c) => Params v o c > Vector v > Vector v > (c, [o])
 allChanges :: (Monoid c, Ord c) => Params v o c > Vector v > Vector v > ChangeMatrix o c
 strParams :: Params Char (String, Int, Char) (Sum Int)
Types
Operations invoked by the WagnerFischer 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
)
Params  

type ChangeMatrix o c = Vector (c, [o]) Source
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
rowmajor format with an additional row and column corresponding to the
empty prefix of the source and destination Vectors
.
Operations
:: (Monoid c, Ord c)  
=> Params v o c  
> Vector v  "Source" vector. 
> Vector v  "Destination" vector. 
> (c, [o]) 
O(nm). Find the cost and optimal edit script to transform one Vector
into another.
:: (Monoid c, Ord c)  
=> Params v o c  
> Vector v  "Source" vector. 
> Vector v  "Destination" vector. 
> ChangeMatrix o c 
O(nm). Calculate the complete matrix of edit scripts and costs between two vectors.