module Exercise_4 where

import Data.List

{-H4.1.10-}
editDistance :: Eq a => [a] -> [a] -> Int
editDistance [] [] = 0
editDistance [] s2 = length s2
editDistance s1 [] = length s1
editDistance s1 s2 | last s1 == last s2 = editDistance (init s1) (init s2)
                   | otherwise = minimum [1 + editDistance (init s1) s2,
                                          1 + editDistance s1 (init s2),
                                          1 + editDistance (init s1) (init s2),
                                          if length s1 > 1 && length s2 >1 && s1 !! (length s1 - 2) == last s2 && last s1 == s2 !! (length s2 - 2) then 1 + editDistance (take (length s1 - 2) s1) (take (length s2 - 2) s2) else 99 
                                          ]


{-H4.1.11-}
{-WETT-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect xs ys = let c = [[editDistance x y|y<-ys]|x<-xs]
                         in let b = [minimum c1|c1<- transpose c] 
                            in let h = [elemIndices b1 c1|(b1,c1)<-zip b $ transpose c]
                                in [[xs !! h2|h2<-h1]|h1<-h]

{-TTEW-}