module Exercise_4 where
import Data.List
import Data.Function
import Data.Array

{-H4.1.10-}
editDistance :: Eq a => [a] -> [a] -> Int
editDistance [] _ = 0
editDistance _ [] = 0
editDistance a b =   aux a b (length a) (length b)
    where aux a b i j = minimum ([ 0 | i == j,i == 0] ++ [(aux a b (i-1) j ) + 1 | i > 0 ] ++ [(aux a b i (j-1)) + 1 | j > 0 ] ++ [ aux a b (i-1) (j-1) | i > 0 && j > 0 && ((a !! (i - 1)) == (b !! (j - 1)))] ++ [(aux a b (i-1) (j-1))  + 1 | i > 0 && j > 0 && ((a !! (i - 1)) /= (b !! (j - 1)))] ++ [(aux a b (i-2) (j-2) ) + 1 | i > 1 && j > 1 && ((a !! (i - 1)) == (b !! (j - 2))) && ((a !! (i - 2)) == (b !! (j - 1)))])
 
{-H4.1.11-}
{-WETT-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect [] _ =[]
spellCorrect _ []=[]
spellCorrect xs ys = [[ fst x | x <- distanceList xs y ] | y <-ys ] 

distanceList ::[String] -> String -> [(String,Int)]             
distanceList xs y = takeWhile(\(x,y) -> (y == snd (head ys) )) ys  
            where ys = sortBy (compare `on` snd) [(p,(editDistances p y)) | p <-xs]

editDistances :: Eq a => [a] -> [a] -> Int
editDistances xs ys = m ! (( length xs ) ,(length ys ))
          where m = listArray ((0,0),(length xs , length ys )) [ aux xs ys i j | (i,j) <- range ((0,0),(length xs , length ys)) ]
                aux xs ys 0 0 = 0 
                aux xs ys i j 
                    | min i j == 0 = max i j 
                    | otherwise = minimum ([0 | i == 0 , j == 0] ++ [(m ! ( (i-1) ,j ) ) + 1 | i > 0 ] ++ [( m !( i , (j-1))) + 1 | j > 0 ] ++ [(m ! (i-1,j-1))+1 | (xs !! (i-1) /= (ys !! (j-1) ))] ++ [(m ! (i-1,j-1)) | (xs !! (i-1) == (ys !! (j-1) ))] ++ [(m ! (i-2,j-2))+1 | i > 1 && j > 1 && (xs !! (i-1) == (ys !! (j-2) )) && (xs !! (i-2) == (ys !! (j-1) )) ] ) 

{-TTEW-}