module Exercise_4 where

import Data.List
import Data.Function

{-H4.1.10-}
--using dynamic programming on a matrix
editDistance :: Eq a => [a] -> [a] -> Int
editDistance a b
  | a == b = 0 
  | null a = length b
  | null b = length a
  | otherwise = last $ last (calcTable [[0..length b]] 1 0)
  where append xss e = init xss ++ [last xss ++ [e]]
        calcTable xss i j
          -- finish
          | i >  length a = xss
          -- first and second column
          | j == 0 = calcTable (append (xss ++ [[]]) (head (last xss) +1)) i 1
          | j == 1 = calcTable (append xss value1) i 2
          -- second row
          | i == 1 && j <= length b = calcTable (append xss value1) 1 (j+1)
          | i == 1 && j >  length b = calcTable xss 2 0
          -- other rows
          | j <= length b = calcTable (append xss value2) i (j+1)
          -- end of row
          | j >  length b = calcTable xss (i+1) 0
          where value1 = minimum [xss!!(i-1)!!j +1, xss!!i!!(j-1) +1, xss!!(i-1)!!(j-1) + fromEnum(a!!(i-1) /= b!!(j-1))]
                val = if a!!(i-1) == b!!(j-2) && a!!(i-2) == b!!(j-1) then xss!!(i-2)!!(j-2) +1 else length a + length b
                value2 = min value1 val

{-H4.1.11-}
{-WETT-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect _ [] = []
spellCorrect [] _ = []
spellCorrect pattern (w:word) = (sc pattern w (-1) []) : spellCorrect pattern word
     where sc [] _ _ ans = ans
           sc (d:dict) target i ans
               | i == -1       = sc dict target distance [d]
               | distance <  i = sc dict target distance [d]
               | distance == i = sc dict target i (ans ++ [d])
               | distance >  i = sc dict target i ans
               where distance = editDistance d target
{-TTEW-}

{-MCCOMMENT
it seems that with library functions this is faster
donno why, since it should tranversing the array multiple times rather than only once
have tested it a while but the difference is quite small

spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect _ [] = []
spellCorrect xs (y:ys) = sc xs y : spellCorrect xs ys

sc :: [String] -> String -> [String]
sc xs str = strs xs indices
    where ys = (`editDistance` str) <$> xs
          indices = elemIndices (minimum ys) ys
          strs _ [] = []
          strs xs (y:ys) = (xs !! y) : strs xs ys
-}