module Exercise_4 where


{-H4.1.10-}
editDistance :: Eq a => [a] -> [a] -> Int
editDistance a b = dPro a b (length a) (length b)
     
    


dPro ::  Eq a => [a] -> [a] -> Int -> Int -> Int
dPro _ _ 0 0 = 0 
dPro _ _ i 0 = i
dPro _ _ 0 j = j
dPro a b i j = minimum[r | r <- results, r /= -1]
    where
        results = [
            (if i==0 && j==0 then 0 else -1), --redundant
            (if i > 0 then (dPro a b (i-1) j) + 1 else -1),
            (if j > 0 then dPro a b i (j-1) + 1 else -1),
            (if i > 0 && j > 0 && a!!(i-1) == b!!(j-1) 
                then dPro a b (i-1) (j-1) 
                    else -1
            ), 
            (if i > 0 && j > 0 && a!!(i-1) /= b!!(j-1) 
                then dPro a b (i-1) (j-1) + 1 
                    else -1
            ),
            (if i > 1 && j > 1 && a!!(i-1) == b!!(j-2) && a!!(i-2) == b!!(j-1)
                then dPro a b (i-2) (j-2) + 1 
                    else -1
            )
            ]













d ::  Eq a => [a] -> [a] -> Int -> Int -> Int
d _ _ 0 0 = 0 
d a b i j = minimum[r | r <- results, r /= -1]
    where
        results = [
            (if i==0 && j==0 then 0 else -1), --redundant
            (if i > 0 then (d a b (i-1) j) + 1 else -1),
            (if j > 0 then d a b i (j-1) + 1 else -1),
            (if i > 0 && j > 0 && a!!(i-1) == b!!(j-1) 
                then d a b (i-1) (j-1) 
                    else -1
            ), 
            (if i > 0 && j > 0 && a!!(i-1) /= b!!(j-1) 
                then d a b (i-1) (j-1) + 1 
                    else -1
            ),
            (if i > 1 && j > 1 && a!!(i-1) == b!!(j-2) && a!!(i-2) == b!!(j-1)
                then d a b (i-2) (j-2) + 1 
                    else -1
            )
            ]

{-H4.1.11-}
{-WETT-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect _ [] = []
spellCorrect dict (word: ws) = [fst (correctWord dict)] ++ spellCorrect dict ws
    where
        correctWord [] = ([], -1)
        correctWord (c_w : r_dict) 
            | dist < earlyMin || earlyMin == -1 = ([c_w], dist)
            | dist == earlyMin = ([c_w] ++ laterWords, earlyMin) 
            | dist > earlyMin = (laterWords, earlyMin)
            where
                dist = editDistance word c_w
                (laterWords, earlyMin) = correctWord r_dict
            

{-TTEW-}