module Exercise_4 where

{-H4.1.10-}
editDistance :: Eq a => [a] -> [a] -> Int
editDistance xs ys = editDistance2 (reverse xs) (reverse ys)
 where
  editDistance2 xs [] = length xs
  editDistance2 [] ys = length ys
  editDistance2 (x:xs) (y:ys)
   |x == y = editDistance2 xs ys
   |length xs > 0 && length ys > 0 && (x == head ys) && (y == head xs) = minimum [editDistance2 (tail xs) (tail ys) + 1, 1+ editDistance2 (x:xs) ys, 1+ editDistance2 xs (y:ys),1 + editDistance2 xs ys]
   |otherwise = minimum [1+ editDistance2 (x:xs) ys, 1+ editDistance2 xs (y:ys),1 + editDistance2 xs ys]

{-H4.1.11-}
{-WETT-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect xs ys = [spellCorrect2 xs y|y<-ys]
 where
  spellCorrect2 [] _ = []
  spellCorrect2 (x:xs) y = spellCorrect3 xs y (editDistance x y) [x]
   where
    spellCorrect3 [] _ _ zs = zs
    spellCorrect3 (x:xs) y n zs
     |n > a = spellCorrect3 xs y a [x]
     |n == a = spellCorrect3 xs y n (x:zs)
     |otherwise = spellCorrect3 xs y n zs
      where a = editDistance x y
{-TTEW-}