| Paste number 32161: | Levenshtein distance |
| Pasted by: | Saizan |
| 2 years, 3 weeks ago | |
| None | |
| Paste contents: |
| import Data.List lev ss ts = fst . last . foldl' aux (zipWith (,) [0..] (' ':ss)) $ zipWith (,) [1..] ts where aux ss' (n,t) = let r = (n,' '): zipWith3 aux' r ss' (tail ss') aux' (pr,_) (pc,_) (cc,s) = let cost = if s == t then 0 else 1 in (minimum [pr+1,pc+cost,cc+1],s) in r |
Annotations for this paste:
| Annotation number 1: | better names, and comments |
| Pasted by: | Saizan |
| 2 years, 3 weeks ago | |
| Paste contents: |
| import Data.List lev :: (Num a, Enum a, Ord a) => [Char] -> [Char] -> a lev ss ts = fst . last . foldl' nextRow (zip [0..] (' ':ss)) $ zip [1..] ts -- folds on the first column building the rows where nextRow ss' (n,t) = let r = (n,' '): zipWith3 takemin r ss' (tail ss') -- build the current row travelling throgh the previous takemin (pr,_) (pc,_) (cc,s) = let cost = if s == t then 0 else 1 -- comparing each element with the one on the first column in (minimum [pr+1,pc+cost,cc+1],s) in r |