module Exercise_4 where

import Data.List
import Data.Maybe

{-WETT-}
{-H4.1.10-}
editDistance :: Eq a => [a] -> [a] -> Int
editDistance xs ys = editDistanceAcc xs ys (length xs) (length ys)
  where
    editDistanceAcc xs ys i j
      | i == 0 = j
      | j == 0 = i
      | i > 0 && j > 0 && xs !! (i - 1) == ys !! (j - 1) = editDistanceAcc xs ys (i - 1) (j - 1)
      | i > 1 && j > 1 && xs !! (i - 1) == ys !! (j - 2) && xs !! (i - 2) == ys !! (j - 1) = 1 + (min (editDistanceAcc xs ys (i - 2) (j - 2)) (min (editDistanceAcc xs ys i (j - 1)) (min (editDistanceAcc xs ys (i - 1) j) (editDistanceAcc xs ys (i - 1) (j - 1)))))
      | otherwise = 1 + (min (editDistanceAcc xs ys i (j - 1)) (min (editDistanceAcc xs ys (i - 1) j) (editDistanceAcc xs ys (i - 1) (j - 1))))

{-H4.1.11-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect d xs = spellCorrectAcc (countEditDistances d xs)
  where
    countEditDistances d xs = [[(de, editDistance de x) | de <- d] | x <- xs]
    spellCorrectAcc [] = []
    spellCorrectAcc (x:xs) = let (_, editDistances) = unzip x
                                 minDistance = minimum editDistances in
      [[de | (de, editDistance) <- x, editDistance == minDistance]] ++ (spellCorrectAcc xs)  
{-TTEW-}

{--effEditDistance :: Eq a => [a] -> [a] -> Int
effEditDistance xs ys = effEditDistanceAcc xs ys (length xs) (length ys)
  where
    effEditDistanceAcc xs ys i j = let--}