Skip to content

Instantly share code, notes, and snippets.

@tixxit
Created September 28, 2011 03:10
Show Gist options
  • Save tixxit/1246894 to your computer and use it in GitHub Desktop.
Save tixxit/1246894 to your computer and use it in GitHub Desktop.
Short Levenshtein distance implementation in Scala
package net.tixxit.levenshtein
import scala.math.min
object EditDistance {
def editDist[A](a: Iterable[A], b: Iterable[A]) =
((0 to b.size).toList /: a)((prev, x) =>
(prev zip prev.tail zip b).scanLeft(prev.head + 1) {
case (h, ((d, v), y)) => min(min(h + 1, v + 1), d + (if (x == y) 0 else 1))
}) last
}
@lou-k
Copy link

lou-k commented Dec 5, 2019

/: is foldLeft

@Samuel-William
Copy link

Could you please give an example of usage please?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment