{-

Notes on Haskell.  

To compile this file:  ghc leven.hs
To load into ghci: 
ghci
:load leven.hs
:reload
:?   for help
:t   to see the type of an object
:q   to quit

-}

-- computeLeven and cell work on VERY short strings only!
-- too much recursion, but it's not tail recursion, and no DP
computeLeven :: String -> String -> Int
computeLeven s t = 
  let
    slen = length s
    tlen = length t
  in
    cell slen tlen s t

cell :: Int -> Int -> String -> String -> Int
cell 0 j s t = j
cell i 0 s t = i
cell i j s t = let
                 above  = 1 + cell (i-1) j s t
                 left   = 1 + cell i (j-1) s t
                 cost = if (s!!(i-1) == t!!(j-1)) then 0 else 1
                 corner = cost + cell (i-1) (j-1) s t
               in
                 minimum [above, left, corner]

mainSave = do
  let str1 = "scattered"
  let str2 = "craters"
  let len1 = length str1
  let len2 = length str2
  let answer = computeLeven str1 str2
  putStrLn ("string "++show(str1)++" is of length "++show(len1))
  putStrLn ("string "++show(str2)++" is of length "++show(len2))
  putStrLn ("Levenshtein distance is "++show(answer))

-- nextrow uses the previous row of the table to build the next row
-- temp lets us access the cell to the left
nextrow :: [Int] -> Int -> String -> String -> [Int]
nextrow lastrow rowsToGo s t =
  let
    tlen = length t
    i = length s -rowsToGo
    cost = 0:map (\j -> if s!!(i-1) == t!!(j-1) then 0 else 1) [1..tlen]
    temp = i:map (\j -> min (cost!!j + lastrow!!(j-1))
                            (1+lastrow!!j)) [1..tlen]
  in i:map (\j -> min (1+temp!!(j-1)) (temp!!j) ) [1..tlen]

doRows :: [Int] -> Int -> String -> String -> [Int]
doRows lastRow rowsToGo s t = 
  let
    thisRow = nextrow lastRow rowsToGo s t
  in if (rowsToGo == 0) then thisRow
     else doRows thisRow (rowsToGo-1) s t

test2 = do
  -- let s = "rat"     
  let s = "scattered"
  -- let t = "cat"     
  let t = "craters"
  let slen = length s
  let tlen = length t
  let lastRow = doRows [0..tlen] (slen-1) s t
  putStrLn ("Levenshtein distance is "++show(lastRow!!(tlen)))

main = do
  -- best to use only IO and let statements in main
  --[f1,f2]  <- getArgs
  let f1 = "wc.hs"
  let f2 = "wc.hs"
  str1     <- readFile f1
  --let str1 = "scattered"
  str2     <- readFile f2
  --let str2 = "craters"
  let len1 = length str1
  let len2 = length str2
  --putStrLn ("file "++show(f1)++" is of length "++show(len1))
  --putStrLn ("string "++show(str1)++" is of length "++show(len1))
  putStrLn ("str1 is of length "++show(len1))
  --putStrLn ("file "++show(f2)++" is of length "++show(len2))
  --putStrLn ("string "++show(str2)++" is of length "++show(len2))
  putStrLn ("str2 is of length "++show(len2))
  let lastRow = doRows [0..len2] (len1-1) str1 str2
  putStrLn ("Levenshtein distance is "++show(lastRow!!(len2)))