module Exercise_4 where

import Data.List

{-H4.1.10-}
editDistance :: Eq a => [a] -> [a] -> Int
editDistance a b = 
    let     helper [] [] n = n
            helper [] (_:ys) n = helper [] ys (n+1)
            helper (_:xs) [] n = helper xs [] (n+1)
            helper (x:xx:xs) (y:yy:ys) n = minimum (d:e:f:g:h:[])
                where   d = helper (x:xx:xs) (yy:ys) (n+1)
                        e = helper (xx:xs) (y:yy:ys) (n+1)
                        f = if x == y then helper (xx:xs) (yy:ys) n else maxBound :: Int
                        g = if x /= y then helper (xx:xs) (yy:ys) (n+1)  else maxBound :: Int
                        h = if x == yy && y == xx then helper xs ys (n+1) else maxBound :: Int
            helper (x:xs) (y:ys) n = minimum (d:e:f:g:[])
                where   d = helper (x:xs) ys (n+1)
                        e = helper xs (y:ys) (n+1)
                        f = if x == y then helper xs ys n else maxBound :: Int
                        g = if x /= y then helper xs ys (n+1)  else maxBound :: Int
    in helper (reverse a) (reverse b) 0

{-H4.1.11-}
{-WETT-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect l1 l2 = hel l1 l2 []
    where   hel _ [] ret = reverse ret
            hel l (x:xs) ret = hel l xs (( helper l [] x):ret)
            helper [] [] _ = []
            helper [] a _ = reverse a 
            helper (d:ds) [] x = helper ds [d] x
            helper (d:ds) (e:es) x  | editDistance e x > editDistance d x = helper ds [d] x 
                                    | editDistance e x == editDistance d x = helper ds (d:e:es) x 
                                    | otherwise = helper ds (e:es) x 
{-TTEW-}