module Exercise_4 where

    import Data.List
    import Data.Ratio
    import Data.Maybe
    
    {-H4.1.10-}
    editDistance :: Eq a => [a] -> [a] -> Int
    editDistance [] [] = 0
    editDistance [] w2 = length w2
    editDistance w1 [] = length w1
    editDistance [c1] [c2] = fromEnum (c1 /= c2)
    editDistance [c1] (c2: w2) = length w2 + 1 - fromEnum(c1 `elem` (c2: w2))
    editDistance (c1: w1) [c2] = length w1 + 1 - fromEnum(c2 `elem` (c1: w1))
    editDistance (c1: c1' : w1) (c2: c2' : w2)
        | null (intersect (c1: c1': w1) (c2: c2' : w2)) = max (length (c1: c1': w1)) (length (c2: c2' : w2))
        | c1 == c2 = editDistance (c1': w1) (c2': w2)
        | otherwise = min (min (min (editDistance (c1': w1) (c2': w2)) (editDistance (c1: c1': w1) (c2': w2))) (editDistance (c1': w1) (c2: c2': w2))) (if (c1 == c2' && c1' == c2) then (editDistance w1 w2) else 100000) + 1
    
    {-H4.1.11-}
    {-WETT-}
    spellCorrect'' :: [String] -> String -> Int -> [(String, Int)]
    spellCorrect'' _ [] _ = []
    spellCorrect'' [] _ _ = []
    spellCorrect'' (de: dictionary) word min
        | abs((length word) - (length de)) > min = spellCorrect'' dictionary word min
        | dist <= min = (de, dist): spellCorrect'' dictionary word dist
        | otherwise = spellCorrect'' dictionary word min
            where dist = editDistance de word


    spellCorrect' :: [String] -> String -> [String]
    spellCorrect' dictionary word = map (\x -> fst x) (filter(\(_,y) -> y == snd (last res)) res) where res = spellCorrect'' dictionary word 10000
    
    spellCorrect :: [String] -> [String] -> [[String]]
    spellCorrect dictionary words = [spellCorrect' dictionary word | word <- words] where
    {-TTEW-}