module Exercise_4 where
    import Data.List
    import Data.Maybe

    {-H4.1.10-}
    editDistance :: Eq a => [a] -> [a] -> Int
    editDistance a b = inner (length a) (length b) where
        inner i j
            | i == 0 && j == 0 = 0
            | i > 0 && j <= 0 = (inner (i-1) j) + 1
            | i <= 0 && j > 0 = (inner i (j-1)) + 1
            | i > 1 && j > 1 && (a !! (i-1)) == b !! (j-2) && (a !! (i-2)) == b !! (j-1) =
                if (a !! (i-1)) == b !! (j-1) then min (min (inner (i-1) (j-1)) (min ((inner (i-1) j) + 1) ((inner i (j-1)) + 1))) ((inner (i-2) (j-2)) + 1)
                else min (min ((inner (i-1) (j-1)) + 1) (min ((inner (i-1) j) + 1) ((inner i (j-1)) + 1))) ((inner (i-2) (j-2)) + 1)
            | i > 0 && j > 0 && (a !! (i-1)) == b !! (j-1) = min (inner (i-1) (j-1)) (min ((inner (i-1) j) + 1) ((inner i (j-1)) + 1))
            | i > 0 && j > 0 && (a !! (i-1)) /= b !! (j-1) = min ((inner (i-1) (j-1)) + 1) (min ((inner (i-1) j) + 1) ((inner i (j-1)) + 1))

    {-H4.1.11-}
    {-WETT-}
    spellCorrect :: [String] -> [String] -> [[String]]
    spellCorrect _ [] = []
    spellCorrect d (x:xs) = let distances = map (\y -> (y, editDistance y x)) d in
                            let m = foldl (\y z -> if snd z < y then snd z else y) (snd $ head distances) distances in
                            [fst x | x <- distances, snd x == m] : (spellCorrect d xs)
    {-TTEW-}