levenstein.hs

{-# LANGUAGE OverloadedStrings #-}

import Data.HashMap.Lazy
import Data.Text hiding (last, minimum)
import Prelude   hiding (length)

levenstein :: Text -> Text -> Int
levenstein a b = snd $ last levsl
  where
  subo      = (-1, -1)
  delo      = (-1,  0)
  inso      = ( 0, -1)

  offsets   = [subo, delo, inso]
  levsl     = [ ((i, j), lev i j) | j <- uptop b, i <- uptop a ]
  uptop x   = [0 .. length x - 1]
  levsv     = fromList levsl
  off   i j = \(oi, oj) -> (i + oi, j + oj)
  lev   0 j = j
  lev   i 0 = i
  lev   i j | (index a i) == (index b j) = levsv ! off i j subo
            | otherwise            = 1 + minimum [ levsv ! off i j o | o <- offsets]

main :: IO ()
main = print $ levenstein "hello" "world"