Haskell edit distance

edit_distance_haskell.md

These functions are taken from https://wiki.haskell.org/Edit_distance, but cleaned up so they're copy-paste-able.

efficient_edit_distance.hs

-- O(length a * (1 + dist a b))

dist :: Eq a => [a] -> [a] -> Int
dist a b
    = last (if lab == 0 then mainDiag
               else if lab > 0 then lowers !! (lab - 1)
                    else{- < 0 -}   uppers !! (-1 - lab))
    where mainDiag = oneDiag a b (head uppers) (-1 : head lowers)
          uppers = eachDiag a b (mainDiag : uppers) -- upper diagonals
          lowers = eachDiag b a (mainDiag : lowers) -- lower diagonals
          eachDiag a [] diags = []
          eachDiag a (bch:bs) (lastDiag:diags) = oneDiag a bs nextDiag lastDiag : eachDiag a bs diags
              where nextDiag = head (tail diags)
          oneDiag a b diagAbove diagBelow = thisdiag
              where doDiag [] b nw n w = []
                    doDiag a [] nw n w = []
                    doDiag (ach:as) (bch:bs) nw n w = me : (doDiag as bs me (tail n) (tail w))
                        where me = if ach == bch then nw else 1 + min3 (head w) nw (head n)
                    firstelt = 1 + head diagBelow
                    thisdiag = firstelt : doDiag a b firstelt diagAbove (tail diagBelow)
          lab = length a - length b
          min3 x y z = if x < y then x else min y z

standard_edit_distance.hs

-- O(m*n)

import qualified Data.Array as A

editDistance :: Eq a => [a] -> [a] -> Int
editDistance xs ys = table A.! (m,n)
    where
    (m,n) = (length xs, length ys)
    x     = A.array (1,m) (zip [1..] xs)
    y     = A.array (1,n) (zip [1..] ys)

    table :: A.Array (Int,Int) Int
    table = A.array bnds [(ij, dist ij) | ij <- A.range bnds]
    bnds  = ((0,0),(m,n))

    dist (0,j) = j
    dist (i,0) = i
    dist (i,j) = minimum [table A.! (i-1,j) + 1, table A.! (i,j-1) + 1,
        if x A.! i == y A.! j then table A.! (i-1,j-1) else 1 + table A.! (i-1,j-1)]