import Data.List

data Edit = Change Char
            | Insert Char
            | Copy
            | Delete
            | Kill
    deriving (Show)

transform :: String -> String -> [Edit]
transform "" ""                   = []
transform (a:"") (b:"")           = if a == b then [Copy] else [Change b]
transform (a:"") (b:bs)           | a == b = [Copy] ++ transform "" bs
                                  | a == head bs = [Insert b] ++ transform (a:"") bs
                                  | otherwise = [Change b] ++ transform "" bs
transform (a:as) (b:"")           | a == b = [Copy,Kill]
                                  | b == head as = [Delete] ++ transform (tail as) ""
                                  | otherwise = [Change b,Kill]
transform "" (b:"")               = [Insert b]
transform "" (b:bs)               = [Insert b] ++ transform "" bs
transform str1@(a:as) str2@(b:bs) | a == b = [Copy] ++ transform as bs
                                  | a == head bs = [Insert b] ++ transform str1 bs
                                  | b == head as = [Delete] ++ transform (tail as) bs
                                  | otherwise = [Change b] ++ transform as bs

traceTransform :: String -> [Edit] -> String
traceTransform str a = (replicate 16 ' ') ++ str ++ "\n" ++ traceTransformRec str a 0

traceTransformRec :: String -> [Edit] -> Int -> String
traceTransformRec _ [] _ = ""
traceTransformRec str (Copy:as) pos = "Copy" ++ (replicate 12 ' ') ++ str ++ "\n" ++ traceTransformRec str as (pos + 1)
traceTransformRec str (Change a:as) pos = let x = replaceNth pos a str
                                          in "Change '" ++ [a] ++ "'" ++ (replicate 6 ' ') ++ x ++ "\n" ++ traceTransformRec x as (pos + 1)
traceTransformRec str (Insert a:as) pos = let x = take pos str ++ [a] ++ drop pos str
                                          in "Insert '" ++ [a] ++ "'" ++ (replicate 6 ' ') ++ x ++ "\n" ++ traceTransformRec x as (pos + 1)
traceTransformRec str (Delete:as) pos = let x = take pos str ++ drop (pos + 1) str
                                          in "Delete" ++ (replicate 10 ' ') ++ x ++ "\n" ++ traceTransformRec x as (pos + 1)
traceTransformRec str [Kill] pos = "Kill" ++ (replicate 12 ' ') ++ take pos str

replaceNth :: Int -> a -> [a] -> [a]
replaceNth n newVal (x:xs) | n == 0 = newVal:xs
                           | otherwise = x:replaceNth (n-1) newVal xs