module Exercise_4 where


{-H4.1.10-}
editDistance :: Eq a => [a] -> [a] -> Int
editDistance xs ys = dist!!(length xs)!!(length ys)
 where dist = [[if i==0 then j else if j==0 then i 
                               else if xs!!(i-1)==ys!!(j-1) then dist!!(i-1)!!(j-1) 
                               else if i>1 && j>1 && xs!!(i-1)==ys!!(j-2) && xs!!(i-2)==ys!!(j-1)
                               then 1+minimum[dist!!(i-2)!!(j-2), dist!!(i-1)!!j, dist!!i!!(j-1)]
                               else 1+minimum[dist!!i!!(j-1), dist!!(i-1)!!j , dist!!(i-1)!!(j-1)]|j<-[0..length ys]]|i<-[0..length xs]]

{-H4.1.11-}
{-WETT-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect _ [] = []
spellCorrect (d:ds) xs = [findmin ds x (editDistance d x) [d]| x<-xs]
 where findmin [] _ _ ls = ls
       findmin (y:ys) x mindist ls
        |distance < mindist = findmin ys x distance [y]
        |distance == mindist = findmin ys x mindist (y:ls)
        |otherwise = findmin ys x mindist ls
         where distance=editDistance y x
{-TTEW-}