module Exercise_4 where

editDistance :: Eq a => [a] -> [a] -> Int
editDistance xs ys = internal xs ys (length xs) (length ys)
 where
  internal xs ys i j
   | i == 0 && j == 0 = 0
   | i == 0 = intB + 1
   | j == 0 = intA + 1
   | i == 1 || j == 1 = minimum [intA + 1, intB + 1, if xs!!(i - 1) == ys!!(j - 1) then intC else intC + 1]
   | xs!!(i - 1) == ys!!(j - 2) && xs!!(i - 2) == ys!!(j - 1) = minimum [intA + 1, intB + 1, (if xs!!(i - 1) == ys!!(j - 1) then intC else intC + 1), intD + 1]
   | otherwise = minimum [intA + 1, intB + 1, if xs!!(i - 1) == ys!!(j - 1) then intC else intC + 1]
    where
     intA = internal xs ys (i - 1) j
     intB = internal xs ys i (j - 1)
     intC = internal xs ys (i - 1) (j - 1)
     intD = internal xs ys (i - 2) (j - 2)

{-H4.1.11-}
{-WETT-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect dir xs = strip [minSet [(editDistance entry x, entry) | entry <- dir] | x <- xs]
 where
  strip :: [[(Int, String)]] -> [[String]]
  strip xss = [[snd x | x <- xs] | xs <- xss]
  minSet :: [(Int, String)] -> [(Int, String)]
  minSet (x:xs)
   | null xs = [x]
   | fst x < fst (head next) = [x]
   | fst (head next) < fst x = next
   | otherwise = [x]++next
    where next = minSet xs
{-TTEW-}