package scalaz

/**
 * <ol>
 * <li>(distance(a, b) == 0) == (a == b)</li>
 * <li>Commutativity: distance(a, b) == distance(b, a)</li>
 * <li>Triangle Equality: distance(a, b) + distance(b, c) >= distance(a, c)</li>
 * </ol>
 */
sealed trait MetricSpace[-A] {
  def distance(a1: A, a2: A): Int
}

trait MetricSpaces {
  def metricSpace[A](f: (A, A) => Int): MetricSpace[A] = new MetricSpace[A] {
    def distance(a1: A, a2: A) = f(a1, a2)
  }

  import Scalaz._

  def levenshtein[M[_], A](implicit l: Length[M], i: Index[M], e: Equal[A]): MetricSpace[M[A]] = metricSpace[M[A]](_ <---> _)

  implicit def levenshteins: MetricSpace[String] = levenshtein[List, Char]  ((s: String) => s.toList)
}