module Exercise_4 where

import Data.List

{-H4.1.10-}
editDistance :: Eq a => [a] -> [a] -> Int
editDistance xs ys =  editDistanceAux xs ys (length xs) (length ys) 
    
editDistanceAux :: Eq a => [a] -> [a] -> Int -> Int -> Int
editDistanceAux as bs i j
  |i == 0 = j
  |j == 0 = i
  |as!!(i-1) == bs!!(j-1) = editDistanceAux as bs (i-1) (j-1)
  |otherwise = 1+  minimum (([editDistanceAux as bs i (j-1), editDistanceAux as bs (i-1) j, editDistanceAux as bs (i-1) (j-1)]) ++
  (if i > 1 && j > 1 && as!!(i-1) == bs!!(j-2) && as!!(i-2) == bs!!(j-1) then [editDistanceAux as bs (i-2) (j-2) ] else []))

  -- |i == j && i == 0 = 0
  -- |i > 1 && j > 1 && as!!(i-1) == bs!!(j-2) && as!!(i-2) == bs!!(j-1) = editDistanceAux as bs (i-2) (j-2) + 1
  -- |i > 0 = 1 + editDistanceAux as bs (i-1) j
  -- |j > 0 = 1 + editDistanceAux as bs i (j-1)
  -- |i > 0 && j > 0 && as!!(i-1) /= bs!!(j-1) = editDistanceAux as bs (i-1) (j-1) + 1
  -- |i > 0 && j > 0 && as!!(i-1) == bs!!(j-1) = editDistanceAux as bs (i-1) (j-1) 
  
{-H4.1.11-}
{-WETT-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect _ [] = []
spellCorrect xs (y:ys)= [z|z<-xs, editDistance z y == d] : spellCorrect xs ys where d = minimum [editDistance a y | a<-xs]
{-TTEW-}