module Exercise_4 where

import Data.List

{-H4.1.10-}
editDistance :: Eq a => [a] -> [a] -> Int
editDistance a b = editDistance' a b (length a) (length b) 

editDistance' :: Eq a => [a] -> [a] -> Int -> Int -> Int
editDistance' a b i j 
  |i > 0 && j == 0 = (editDistance' a b (i-1) j)+1
  |i == 0 && j > 0 = (editDistance' a b i (j-1))+1
  |(i >= 1 && j == 1)||(i == 1 && j >= 1) = 
    if (a!!(i-1)) == (b!!(j-1)) 
	then  minimum [(editDistance' a b (i-1) (j-1)),((editDistance' a b (i-1) j)+1),((editDistance' a b i (j-1))+1)] 
	else minimum [((editDistance' a b (i-1) (j-1))+1),((editDistance' a b (i-1) j)+1),((editDistance' a b i (j-1))+1)]
  |i > 1 && j > 1 && (a!!(i-1)) == (b!!(j-1)) && ((a!!(i-1)) /= (b!!(j-2)) || (a!!(i-2)) /= (b!!(j-1))) = 
    minimum [(editDistance' a b (i-1) (j-1)),((editDistance' a b (i-1) j)+1),((editDistance' a b i (j-1))+1)]
  |i > 1 && j > 1 && (a!!(i-1)) /= (b!!(j-1)) && ((a!!(i-1)) /= (b!!(j-2)) || (a!!(i-2)) /= (b!!(j-1))) = 
    minimum [((editDistance' a b (i-1) (j-1))+1),((editDistance' a b (i-1) j)+1),((editDistance' a b i (j-1))+1)]
  |i > 1 && j > 1 && (a!!(i-1)) == (b!!(j-2)) && (a!!(i-2)) == (b!!(j-1)) = 
    if (a!!(i-1)) == (b!!(j-1)) 
	then minimum [(editDistance' a b (i-1) (j-1)),((editDistance' a b (i-1) j)+1),((editDistance' a b i (j-1))+1),((editDistance' a b (i-2) (j-2))+1)] 
	else minimum [((editDistance' a b (i-1) (j-1))+1),((editDistance' a b (i-1) j)+1),((editDistance' a b i (j-1))+1),((editDistance' a b (i-2) (j-2))+1)]
  |otherwise = 0
editDistance' [] b i j = j
editDistance' a [] i j = i
{-H4.1.11-}
{-WETT-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect d xs 
  |null xs = []
  |otherwise = let x = sortOn snd (spellCorrect' d (head xs)) in [minimumSet x (snd( head( sortOn snd x)))] ++ spellCorrect d (tail xs)

spellCorrect' :: [String] -> String -> [(String,Int)]
spellCorrect' d x 
  |null d = []
  |otherwise = [((head d),editDistance (head d) x )] ++ spellCorrect' (tail d) x
  
minimumSet :: [(String, Int)] -> Int -> [String]
minimumSet xs i
  |null xs =[]
  |otherwise = if (snd(head xs)) == i then [fst(head xs)] ++ minimumSet (tail xs) i else minimumSet (tail xs) i 
{-TTEW-}