module Exercise_4 where
import Data.List
import Data.Array (listArray,range,(!))

{-H4.1.10-}
editDistance :: Eq a => [a] -> [a] -> Int
editDistance a b  = d m n
  where (m,n) =(length a, length b)
        d 0 0 = 0
        d 0 j = j
        d i 0 = i
        d i j  = minimum [hd ! (i-1,j) +1 ,hd ! (i,j-1) + 1, if a !!(i-1) == b !!(j-1) then  hd ! (i-1,j-1) else hd ! (i-1,j-1) + 1 , if i>1 && j>1 && a !!(i-1) == b !!(j-2) && a !!(i-2) == b !!(j-1) then hd ! (i-2,j-2) + 1 else m+n ]
        hd = listArray bounds [d i j | (i,j)<-(range bounds)]
        bounds = ((0, 0), (m, n))

{-H4.1.11-}
{-WETT-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect dict xs  = [ help $ sortBy (\(_,a)(_,b)-> compare a b) $map (\w->(w,editDistance x w)) (filter (\w-> (length w <= length x * 2)) dict)|x<-xs]
  where help ::[(String,Int)]-> [String]
        help xs = let s = snd (head xs) in  map fst $ takeWhile (\(_,x)->x == s) xs
{-TTEW-}