-- Computes the edit distance between two strings in a naive (exponential) way 
-- and a memoized way.  (Dynamic programming, which you will learn about in CS 25,
-- is a better way of implementing the memoization.)

-- This version uses a state Monad to keep track of the solved problems.  Compare
-- it to EditDistance.hs.

-- based on a program by Michael Fromberger, 11/07
-- modified and extended by Scot Drysdale, 11/18/07
-- Converted to state Modad by Scot Drysdale, 2/28/08

-- The idea is to convert a string s1 into a second string s2 using the smallest number
-- of edit operations (or in general the smallest cost series of edit operations).
-- This version of edit distance allows four operations, each of which is charged 
-- a cost of one.   (This could be easily modified to have different costs.)
-- The operations are:
--   1) Insert a character
--   2) Delete a character
--   3) Replace a character
--   4) Swap two characters to match the output.


module EditDistance 
where

import MemoS

-- Memoized implementation of edit distance; quadratic number of Map inserts and lookups.
memoEditDistance :: String -> String -> Int
memoEditDistance s1 s2 = runMemo eDist (s1,s2)

-- Helper function
-- Note that in this version the Map is passed as state in the state Monad.
eDist         :: MemoFunction (String,String) Int
eDist (s1, []) = return (length s1)            -- Delete remaining characters in s1
eDist ([], s2) = return (length s2)            -- Insert remaining characters in s2
eDist (s1@(c1:cs1), s2@(c2:cs2)) = 
  do 
    matchDist <- callMemo eDist (cs1, cs2)        -- subproblem for match and replace 
    delDist   <- callMemo eDist (cs1, s2)
    insDist   <- callMemo eDist (s1, cs2)
    swapDist  <-  case (cs1, cs2) of
                    (c1' : cs1', c2' : cs2')
                        | c1' == c2 && c2' == c1 ->
                            callMemo eDist (cs1', cs2')
                        | otherwise -> return (insDist + 2)  -- so won't be minimum
                    _ -> return (insDist + 2)
    return (minimum [if c1 == c2 then matchDist else matchDist + 1,
                               delDist + 1, insDist + 1, swapDist + 1])