Haskell实现Levenshtein距离：如何组织distance与levenshtein函数？

Hey there! Let's work through your problem with accessing variables in the where clause first, then dive into some improvements for your Haskell Levenshtein code.

The Variable Access Issue #

When you tried moving distance into levenshtein's where clause, you couldn't access size, coordinates, w1, or w2 because those variables are scoped to levenshtein's body. The fix is straightforward: define distance directly inside levenshtein's where block, so it can capture all those outer variables naturally.

Also, your original distance function had a few State monad logic issues (like trying to put matrix when the state is an index, not the matrix itself). Let's fix that too. Here's how the adjusted levenshtein function would look with distance in the right place:

import Data.Matrix
import Control.Monad.State

type RecState = Int

setLeftCol :: String -> Matrix Int -> Matrix Int
setLeftCol str mat = foldl (\m idx -> setElem (idx - 1) (idx, 1) m) mat [1..length str + 1]

setTopRow :: String -> Matrix Int -> Matrix Int
setTopRow str mat = transpose $ setLeftCol str $ transpose mat

coords :: Int -> Int -> [(Int,Int)]
coords width height = [(x,y) | x <- [2..(width+1)], y <- [2..(height+1)]]

levenshtein :: String -> String -> Int
levenshtein "" "" = 0
levenshtein "" w2 = length w2
levenshtein w1 "" = length w1
levenshtein w1 w2 = 
  let lenW1 = length w1
      lenW2 = length w2
      size = lenW1 * lenW2
      initialMatrix = setTopRow w2 $ setLeftCol w1 $ zero (lenW1 + 1) (lenW2 + 1)
      coordinates = coords lenW1 lenW2
  in getElem (lenW1 + 1) (lenW2 + 1) $ execState (distance initialMatrix) 0
  where
    distance :: Matrix Int -> State RecState (Matrix Int)
    distance matrix = do
      index <- get
      if index >= size
        then return matrix
        else do
          put (index + 1)
          let (i, j) = coordinates !! index
              ch1 = w1 !! (i - 2)
              ch2 = w2 !! (j - 2)
              cost = if ch1 /= ch2 then 1 else 0
              entry1 = getElem (i - 1) j matrix + 1
              entry2 = getElem i (j - 1) matrix + 1
              entry3 = getElem (i - 1) (j - 1) matrix + cost
              newMatrix = setElem (minimum [entry1, entry2, entry3]) (i, j) matrix
          distance newMatrix

Key fixes here:

• distance is now inside levenshtein's where, so it can access w1, w2, size, and coordinates directly.
• Removed unnecessary Maybe wrapping around the matrix (since our initialization steps use valid coordinates and can't fail).
• Fixed the State logic: we track the current index, increment it each iteration, and return the fully populated matrix once all coordinates are processed.
• The final result pulls the bottom-right element of the matrix, which is the Levenshtein distance.

Implementation Improvements #

Your core idea is solid, but we can simplify the code to make it more idiomatic Haskell:

1. Replace State Monad with Fold #

You don't need the State monad just to iterate over coordinates. A simple foldl will do the same job more clearly, with no monadic overhead:

import Data.Matrix

setLeftCol :: String -> Matrix Int -> Matrix Int
setLeftCol str mat = foldl (\m idx -> setElem (idx - 1) (idx, 1) m) mat [1..length str + 1]

setTopRow :: String -> Matrix Int -> Matrix Int
setTopRow str mat = transpose $ setLeftCol str $ transpose mat

levenshtein :: String -> String -> Int
levenshtein "" "" = 0
levenshtein "" w2 = length w2
levenshtein w1 "" = length w1
levenshtein w1 w2 = 
  let lenW1 = length w1
      lenW2 = length w2
      initialMatrix = setTopRow w2 $ setLeftCol w1 $ zero (lenW1 + 1) (lenW2 + 1)
      coordinates = [(i, j) | i <- [2..lenW1+1], j <- [2..lenW2+1]]
      updateMatrix mat (i, j) =
        let ch1 = w1 !! (i - 2)
            ch2 = w2 !! (j - 2)
            cost = if ch1 /= ch2 then 1 else 0
            entry1 = getElem (i - 1) j mat + 1
            entry2 = getElem i (j - 1) mat + 1
            entry3 = getElem (i - 1) (j - 1) mat + cost
        in setElem (minimum [entry1, entry2, entry3]) (i, j) mat
      finalMatrix = foldl updateMatrix initialMatrix coordinates
  in getElem (lenW1 + 1) (lenW2 + 1) finalMatrix

2. Avoid Partial Functions (Optional) #

Functions like (!!) are partial (they crash if the index is out of bounds). For robustness, you could use safe lookup functions from packages like extra:

import Data.List.Extra (!!?)

ch1 = maybe ' ' id $ w1 !!? (i - 2)
ch2 = maybe ' ' id $ w2 !!? (j - 2)

Since we calculate indices based on string lengths, our code is safe as-is, but this adds an extra layer of bulletproofing.

3. Use More Efficient Data Structures (Optional) #

The Data.Matrix package works well, but if you're looking for better performance, you could use a 2D list (since Levenshtein matrices are dense) or the vector package for mutable arrays. For most use cases, though, Data.Matrix is perfectly acceptable.

内容的提问来源于stack exchange，提问作者emmeowzing