module Exercise_4 where

import Data.List
import Data.Maybe

{-H4.1.10-}
editDistance :: Eq a => [a] -> [a] -> Int
editDistance a b = eD (length a) (length b) where
    eD 0 0 = 0
    eD i 0 = 1 + eD (pred i) 0
    eD 0 j = 1 + eD 0 (pred j)
    eD i j = minimum ( 
        (if i > 0 then [1 + eD (pred i) j] else []) ++
        (if j > 0 then [1 + eD i (pred j)] else []) ++
        (if nthA (pred i) == nthB (pred j) then [eD (pred i) (pred j)] else []) ++
        (if nthA (pred i) /= nthB (pred j) then [1 + eD (pred i) (pred j)] else []) ++
        (if j > 1 && i > 1 && nthA (pred i) == nthB (j -  2) && nthA (i -  2) == nthB (pred j) then [1 + eD (i-2) (j-2)] else []) )
    nthA i = head (drop i a)
    nthB j = head (drop j b)

{-H4.1.11-}
{-WETT-}
spellCorrect :: [String] -> [String] -> [[String]]
spellCorrect (fw:fws) words = map (map fst . snd) (foldl stage2 stage1 fws) where
    stage1 = map (\w -> (w,[(fw, editDistance w fw)])) words
    stage2 acc fw = map stage3 acc where
        stage3 ((w,(aw,d):as)) = if eD<d then (w,[(fw, eD)]) else (if eD == d then (w,(fw,eD):(aw,d):as) else (w,(aw,d):as)) where
            eD = editDistance fw w
{-TTEW-}