module Exercise_4 where

{-H4.1.10-}
editDistance :: Eq a => [a] -> [a] -> Int


editDistance xs ys = mem !! (length xs) !! (length ys)
    where
        mem = [[ed (i,j) | j <- [0..(length ys)]] | i <- [0..(length xs)]]
        ed (i,j) = minimum $ filter (>=0) [c1 i j, c2 i j, c3 i j, c4 i j, c5 i j]
        c1 i j = if i == 0 && j == 0 then 0 else -1
        c2 i j = if i > 0 then (mem !! (i-1) !! j) + 1 else -1
        c3 i j = if j > 0 then (mem !! i !! (j-1)) + 1 else -1
        c4 i j = if i > 0 && j > 0 then if xs !! (i-1) == ys !! (j-1) then (mem !! (i-1) !! (j-1)) else (mem !! (i-1) !! (j-1)) + 1 else -1
        c5 i j = if i > 1 && j > 1 && xs !! (i-1) == ys !! (j-2) && xs !! (i-2) == ys !! (j-1) then (mem !! (i-2) !! (j-2)) + 1 else -1

{-
editDistance xs ys = editDistance' xs ys (length xs) (length ys)
        where 
            editDistance' xs ys i j = minimum $ filter (>=0) [c1 xs ys i j, c2 xs ys i j, c3 xs ys i j, c4 xs ys i j, c5 xs ys i j]
            c1 xs ys i j = if i == 0 && j == 0 then 0 else -1
            c2 xs ys i j = if i > 0 then (editDistance' xs ys (i-1) j) + 1 else -1
            c3 xs ys i j = if j > 0 then (editDistance' xs ys i (j-1)) + 1 else -1
            c4 xs ys i j = if i > 0 && j > 0 then if xs !! (i-1) == ys !! (j-1) then (editDistance' xs ys (i-1) (j-1)) else (editDistance' xs ys (i-1) (j-1)) + 1 else -1
            c5 xs ys i j = if i > 1 && j > 1 && xs !! (i-1) == ys !! (j-2) && xs !! (i-2) == ys !! (j-1) then (editDistance' xs ys (i-2) (j-2)) + 1 else -1
-}

{-H4.1.11-}

{-WETT-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect d xs = [keepMin x | x <- xs]
            where
                keepMin x = keepMin' x (tail d) (editDistance x (head d)) [head d]
                keepMin' x [] mdist vs = vs
                keepMin' x (d:ds) mdist vs
                    | editDistance x d < mdist = keepMin' x ds (editDistance x d) [d]
                    | editDistance x d == mdist = keepMin' x ds mdist (d:vs)
                    | otherwise = keepMin' x ds mdist vs
{-TTEW-}