module Exercise_4 where
  import Data.List
  import Data.Maybe
  import Data.Array

  {-WETT-}
  {-H4.1.10-}
  editDistance :: Eq a => [a] -> [a] -> Int
  editDistance as bs =
    let
      distanceMemo = listArray (0,aLen) (map (\x ->  listArray (0, bLen) (map (distanceRecursion x) [0..bLen])) [0..aLen])

      xs = listArray (0,aLen) as
      ys = listArray (0,bLen) bs
      aLen = length as
      bLen = length bs

      distanceRecursion :: Int -> Int -> Int
      distanceRecursion 0 0 = 0
      distanceRecursion i j  = minimum (
        [(distanceMemo ! (pred i) ! j)        + 1 | i > 0] ++
        [(distanceMemo ! i        ! (pred j)) + 1 | j > 0] ++
        [(distanceMemo ! (pred i) ! (pred j))     | i > 0, j > 0, (xs!(pred i)) == (ys!(pred j))] ++
        [(distanceMemo ! (pred i) ! (pred j)) + 1 | i > 0, j > 0, (xs!(pred i)) /= (ys!(pred j))] ++
        [(distanceMemo ! (i - 2)  ! (j - 2))  + 1 | i > 1, j > 1, (xs!(i - 1)) == (ys!(j - 2)), (xs!(i - 2)) == (ys!(j - 1))])
    in
      distanceMemo ! aLen ! bLen
  {-H4.1.11-}
  spellCorrect :: [String] -> [String] -> [[String]]
  spellCorrect ds xs =
    let
      -- recursively creates tuples of (dictionaryWord, editDistance to dictionaryWord)
      -- and only remembers tuples with smallest editDistance
      -- ==> minimal distance words can be retrieved in one pass
      matchingWordDistanceTuple :: Eq a => [[a]] -> [a] -> [([a], Int)]
      matchingWordDistanceTuple [] _ = []
      matchingWordDistanceTuple (d:ds) x
        | null ds = [(d, editDistance d x)]
        | otherwise =
          let
            dist = editDistance d x
            rest = matchingWordDistanceTuple ds x
            rMin = snd $ head rest
          in (if(dist <= rMin) then [(d, dist)] else [])++(if(dist >= rMin) then rest else []) -- could be cleaner with multiway if
    in
      [map fst (matchingWordDistanceTuple ds x) | x <- xs]
      -- possible optimization: somehow apply fst function directly in recursion so another pass can be safed
  {-TTEW-}