lots of questions

Aaa-notes.md

So what I understand to be your questions:

1. What is a coherency problem?
2. What does over constained code look like / cause?
3. How do you lose your "desired" instance?

A way to step through understanding this problem:

• Oh shit, If I have local type classes, I have to handle crazy wacky cases in my implementation, this will likely have performance and correctness implications (see Coherency.scala)
• What happens if I close over constraint on construction? Oops if I close over it, I end up with OverConstrained code (see OverConstrainedCode.scala) and worse I still have coherency issues, and the ability to lose my intended behavious (LosingAnInstance.scala)
• Oh wow, if I just don't do local type classes, by never define conflicting implicits, and ascribe a single type to each behaviour, everything is simple and just works.

The end of all this, is why worry when there is a really easy and low cost solution. Just wrap up each behaviour, and ascribe it a type. The type maps to a single-globally-coherent behaviour. There are lots of decent tools in scala for doing so (@@ Tags, case class NewTypeWrapper(x: X)). The issue I have with the discussion, is that people think really hard how to hack around these corner cases (closing over instances, not closing over instances, what ever), when it is a complexity easily avoided. Programming is hard enough without tricking ourselves into this rubbish.

All that said, I am not trying to convince you of anything, just trying to lay out the issues. There are even deeper issues once you get past this trivial ones. In particular scalaz's type class hierarchy is totally broken, and forces you to make a trade off between overlapping instances and over-constrained code, which just isn't good enough.

Coherency.scala

case class OrderedList[A] private(xs: List[A]) {
  // this should be O(n) worst case but is O(n log n) to avoid violating constraint and/or losing data
  def +(a: A)(implicit O: Ordering[A]) =
    (a :: xs).sorted

  // this should be O(n) in length of only one of the lists (but is O(m + n log n))
  // this could also lose data if the equality is inconsistent, reguardless of extra sort
  def ++(a: OrderedList[A])(implicit O: Ordering[A]) =
    (xs ++ a.xs).sorted
}

LosingAnInstance.scala

object LosingAnInstance extends App {
  // scala.collection.immutable.TreeSet does what you suggest with closing over Ord
  // but it means I can write code like below. This can happen in far more subtle
  // and insiduous ways if local type classes are a common idiom in your code.

  def reversed =
    implicitly[Ordering[Int]].reverse

  def runContextOne = {
    implicit val IntOrdering: Ordering[Int] =
      reversed
    val start = TreeSet(1, 7, 3, 5)
    println("I am ordered in reverse: " + start)
    val updated = ContextTwo.addOne(start)
    println("What do I look like now? " + updated)
    ()
  }

  object ContextTwo {
    def addOne(s: TreeSet[Int]) =
      s.map(_ + 1)
  }

  runContextOne
}

OverConstrainedCode.scala

object OverConstrainedCode extends App {
  import scalaz._, Scalaz._

  // here is a simplified case of what commonly happens

  case class Good[F[_], A](run: Int => F[A]) {
    def map[B](f: A => B)(implicit F: Functor[F]): Good[F, B] =
      Good(i => run(i).map(f))

    def flatMap[B](f: A => Good[F, B])(implicit F: Monad[F]): Good[F, B] =
      Good(i => run(i).flatMap(a => f(a).run(i)))
  }

  case class Bad[F[_]: Monad, A](run: Int => F[A]) {
    def map[B](f: A => B): Bad[F, B] =
      Bad(i => run(i).map(f))

    def flatMap[B](f: A => Bad[F, B]): Bad[F, B] =
      Bad(i => run(i).flatMap(a => f(a).run(i)))
  }


  // Option is all good to flat map, yay!
  Good[Option, Int](Some.apply).flatMap(n =>
    if (n > 7) Good[Option, Int](Some.apply) else Good[Option, Int](_ => None))

  // Validation isn't a Monad but I can still map, yay!
  type ValidationX[A] = ValidationNel[String, A]
  Good[ValidationX, Int](_.successNel).map(_ + 1)


  // Over constrained =====


  // Option is all good to flat map, yay!
  Bad[Option, Int](Some.apply).flatMap(n =>
    if (n > 7) Bad[Option, Int](Some.apply) else Bad[Option, Int](_ => None))

  // Validation isn't a Monad but I can't construct to map over :(
// doesn't compile
//  Bad[ValidationX, Int](_.successNel).map(_ + 1)

}