module Exercise_4 where

import Data.List (find, group, minimum, minimumBy, nub, replicate, union, words)
import Control.Monad (zipWithM)

{-H4.1.11-}
{-WETT-}
editDistanceAux' :: Eq a => Int -> Int -> [a] -> [a] -> Int
editDistanceAux' b n (x:xs) (y:ys) = let cost = if x == y then 0 else 1 in
  minimum [editDistance' b (n + 1) xs (y:ys) + 1, editDistance' b (n + 1) (x:xs) ys + 1, editDistance' b (n + cost) xs ys + cost]

editDistance' :: Eq a => Int -> Int -> [a] -> [a] -> Int
editDistance' b n _ _ | n > b = (10000)
editDistance' _ _ [] ys = length ys 
editDistance' _ _ xs [] = length xs 
editDistance' b n (y1:y2:ys) (x1:x2:xs) | y1 == x2 && y2 == x1 && x1 /= y1 =
  minimum [editDistance' b (n + 1) ys xs + 1, editDistanceAux' b n (y1:y2:ys) (x1:x2:xs)]
editDistance' b n xs ys = editDistanceAux' b n xs ys

editDistance :: Eq a => [a] -> [a] -> Int
editDistance = editDistance' (10000) 0

minEditDistance' :: Int -> [String] -> String -> [(String, Int)]
minEditDistance' b [] _ = []
minEditDistance' b (d:ds) s = 
    let
        dist_d = editDistance' b 0 d s
        bNew = min b dist_d
        ls = if dist_d <= b then [(d, dist_d)] else []
     in ls ++ minEditDistance' bNew ds s

minEditDistance'' dict s = find (not . null) (map (\b -> minEditDistance' b dict s) $ iterate (+2) 1)

spellCorrectWord' dict s =
    let 
        Just ls = minEditDistance'' dict s
        minD = minimum (map snd ls)
     in [ s | (s, d) <- ls, d == minD ]

spellCorrect d xs = [spellCorrectWord' d x | x<-xs]
{-TTEW-}