module Exercise_4 where

import Data.List

{-H4.1.10-}
editDistance :: Eq a => [a] -> [a] -> Int
editDistance xs ys = editDistanceRec xs ys (length (xs)) (length (ys))
                   where editDistanceRec _ _ 0 0 = 0
                         editDistanceRec xs xy x 0 = 1 + (editDistanceRec xs xy (x-1) 0)
                         editDistanceRec xs xy 0 y = 1 + (editDistanceRec xs xy 0 (y-1))
                         editDistanceRec xs ys x y = if ((xs !! (x-1)) == (ys !! (y-1)))
                                                  then editDistanceRec xs ys (x-1) (y-1)
                                                  else if ((x>1) && (y>1) && (xs !! (x-1)) == (ys !! (y-2)) && (xs !! (x-2)) == (ys !! (y-1))) 
                                                    then (minimum [editDistanceRec xs ys x (y-1), editDistanceRec xs ys (x-1) y, editDistanceRec xs ys (x-1) (y-1), editDistanceRec xs ys (x-2) (y-2)]) + 1
                                                    else (minimum [editDistanceRec xs ys x (y-1), editDistanceRec xs ys (x-1) y, editDistanceRec xs ys (x-1) (y-1)]) + 1

{-H4.1.11-}
{-WETT-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect _ [] = []
spellCorrect d (x:xs) = (sC d x (minimum [editDistance w x| w <- d])) ++ (spellCorrect d xs)
                      where sC d x min = [[word | word <- d, (editDistance word x) == min]]
{-TTEW-}