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
}
@jasonleehodges
Copy link

This is a super awesome implementation and it works really well. I'm having a hard time figuring out what this line does:

(0 to b.size).toList /: a)((prev, x)

Specifically, I can't find anything when searching that describes the /: operator. Think you could lend some help?

@m1stermanager
Copy link

m1stermanager commented Feb 22, 2018

@jasonleehodges http://www.scala-lang.org/api/2.12.3/scala/collection/Seq.html#/:[B](z:B)(op:(B,A)=>B):B

I'm not saying I know a lot about it BUT I am also looking it up and found this

edit: its just a fancy syntax for foldLeft.

@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