Mercurial > hg > toys

changeset 23:d0d6e77cb496

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
haskell/levenshtein: add fuco.hs
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Fri, 17 Apr 2015 17:27:50 -0400
parents 7a1528b6afdf
children 7bcb491ce57e
files haskell/levenshtein/fuco.hs
diffstat 1 files changed, 13 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
new file mode 100644
--- /dev/null
+++ b/haskell/levenshtein/fuco.hs
@@ -0,0 +1,13 @@
+nthRow n len = n : replicate (len - 1) 0
+
+updateRow prev n letter word 
+  = reverse $ foldl (\l@(last:_) (j1,j,cl) 
+                     -> minimum [1 + last, 1 + j, 
+                                 j1 + (if letter == cl then 0 else 1)] : l) [n] p
+  where
+    p = zip3 prev (tail prev) word
+
+leven a b = last $ foldl (\x(n,letter) 
+                          -> updateRow x n letter b) [0..(length b)] (zip [0..] a)
+
+main = print $ leven (show [1..1000]) (show [2..1001])
\ No newline at end of file