Skip to content

Instantly share code, notes, and snippets.

@tixxit
Created September 28, 2011 03:10
Show Gist options
  • Select an option

  • Save tixxit/1246894 to your computer and use it in GitHub Desktop.

Select an option

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
Copy Markdown

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

m1stermanager commented Feb 22, 2018

Copy link
Copy Markdown

@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

lou-k commented Dec 5, 2019

Copy link
Copy Markdown

/: is foldLeft

@Samuel-William

Copy link
Copy Markdown

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