module Exercise_4 where
import Data.List
import Data.Array
import Test.QuickCheck

{-WETT-}
{-H4.1.10-}
editDistance :: Eq a => [a] -> [a] -> Int
editDistance a b = edn (length a) (length b)
  where
    edn :: Int -> Int -> Int
    edn 0 0 = 0
    edn 0 j = j
    edn i 0 = i
    edn i j = minimum (
      (if i > 0 then [1 + edn (i-1) j] else []) ++
      (if j > 0 then [1 + edn i (j-1)] else []) ++
      (if (j > 0) && (i > 0)
        then [(if a !! (i-1) == b !! (j-1) then edn (i-1) (j-1) else 1 + edn (i-1) (j-1))]
        else []) ++
      (if (i > 1) && (j > 1) && (a !!(i-1) == b!!(j-2)) && (a!!(i-2) == b!!(j-1))
        then [1 + edn (i-2) (j-2)]
        else [])
      )



{-H4.1.11-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect hay needles = [minimumWith (editDistance n) hay | n <- needles]

minimumWith :: (a -> Int) -> [a] -> [a]
minimumWith f xs = [ x | (n, x) <- numbered, n == minimum (map fst numbered)]
  where numbered = [ (f x, x) | x <- xs ]
{-TTEW-}