module Exercise_4 where

{-H4.1.10-}
editDistance :: Eq a => [a] -> [a] -> Int
editDistance as [] = length as
editDistance [] bs = length bs
editDistance (a:as) (b:bs)
    | not (null as) && not (null bs) && a == (head bs) && b == (head as) =
        minimum [editDistance (tail as) (tail bs) + 1, 
        editDistance as bs + if a == b then 0 else 1,
        editDistance (a:as) bs + 1, editDistance as (b:bs) + 1]
    | otherwise = minimum [editDistance as bs + if a == b then 0 else 1,
        editDistance (a:as) bs + 1, editDistance as (b:bs) + 1]

{-H4.1.11-}
{-WETT-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect _ [] = []
spellCorrect [] _ = []
spellCorrect xs (y:ys) = [[a | a <- xs, editDistance a y == mini]] ++ spellCorrect xs ys
    where 
        mini = minimum [editDistance w y | w <- xs]
{-TTEW-}