Using context bounds "negatively" to ensure type class instance is absent from scope

Question

tl;dr: How do I do something like the made up code below:

def notFunctor[M[_] : Not[Functor]](m: M[_]) = s"$m is not a functor"

The 'Not[Functor]', being the made up part here.
I want it to succeed when the 'm' provided is not a Functor, and fail the compiler otherwise.

Solved: skip the rest of the question and go right ahead to the answer below.

---

What I'm trying to accomplish is, roughly speaking, "negative evidence".

Pseudo code would look something like so:

// type class for obtaining serialization size in bytes.
trait SizeOf[A] { def sizeOf(a: A): Long }

// type class specialized for types whose size may vary between instances
trait VarSizeOf[A] extends SizeOf[A]

// type class specialized for types whose elements share the same size (e.g. Int)
trait FixedSizeOf[A] extends SizeOf[A] {
  def fixedSize: Long
  def sizeOf(a: A) = fixedSize
}

// SizeOf for container with fixed-sized elements and Length (using scalaz.Length)
implicit def fixedSizeOf[T[_] : Length, A : FixedSizeOf] = new VarSizeOf[T[A]] {
  def sizeOf(as: T[A]) = ... // length(as) * sizeOf[A]
}

// SizeOf for container with scalaz.Foldable, and elements with VarSizeOf
implicit def foldSizeOf[T[_] : Foldable, A : SizeOf] = new VarSizeOf[T[A]] {
  def sizeOf(as: T[A]) = ... // foldMap(a => sizeOf(a))
}

Keep in mind that fixedSizeOf() is preferable where relevant, since it saves us the traversal over the collection.

This way, for container types where only Length is defined (but not Foldable), and for elements where a FixedSizeOf is defined, we get improved performance.

For the rest of the cases, we go over the collection and sum individual sizes.

My problem is in the cases where both Length and Foldable are defined for the container, and FixedSizeOf is defined for the elements. This is a very common case here (e.g.,: List[Int] has both defined).

Example:

scala> implicitly[SizeOf[List[Int]]].sizeOf(List(1,2,3))
<console>:24: error: ambiguous implicit values:
 both method foldSizeOf of type [T[_], A](implicit evidence$1: scalaz.Foldable[T], implicit evidence$2: SizeOf[A])VarSizeOf[T[A]]
 and method fixedSizeOf of type [T[_], A](implicit evidence$1: scalaz.Length[T], implicit evidence$2: FixedSizeOf[A])VarSizeOf[T[A]]
 match expected type SizeOf[List[Int]]
              implicitly[SizeOf[List[Int]]].sizeOf(List(1,2,3))

What I would like is to be able to rely on the Foldable type class only when the Length+FixedSizeOf combination does not apply.

For that purpose, I can change the definition of foldSizeOf() to accept VarSizeOf elements:

implicit def foldSizeOfVar[T[_] : Foldable, A : VarSizeOf] = // ...

And now we have to fill in the problematic part that covers Foldable containers with FixedSizeOf elements and no Length defined. I'm not sure how to approach this, but pseudo-code would look something like:

implicit def foldSizeOfFixed[T[_] : Foldable : Not[Length], A : FixedSizeOf] = // ...

The 'Not[Length]', obviously, being the made up part here.

Partial solutions I am aware of

1) Define a class for low priority implicits and extend it, as seen in 'object Predef extends LowPriorityImplicits'. The last implicit (foldSizeOfFixed()) can be defined in the parent class, and will be overridden by alternative from the descendant class.

I am not interested in this option because I'd like to eventually be able to support recursive usage of SizeOf, and this will prevent the implicit in the low priority base class from relying on those in the sub class (is my understanding here correct? EDIT: wrong! implicit lookup works from the context of the sub class, this is a viable solution!)

2) A rougher approach is relying on Option[TypeClass] (e.g.,: Option[Length[List]]. A few of those and I can just write one big ol' implicit that picks Foldable and SizeOf as mandatory and Length and FixedSizeOf as optional, and relies on the latter if they are available. (source: here)

The two problems here are lack of modularity and falling back to runtime exceptions when no relevant type class instances can be located (this example can probably be made to work with this solution, but that's not always possible)

EDIT: This is the best I was able to get with optional implicits. It's not there yet:

implicit def optionalTypeClass[TC](implicit tc: TC = null) = Option(tc)
type OptionalLength[T[_]] = Option[Length[T]]
type OptionalFixedSizeOf[T[_]] = Option[FixedSizeOf[T]]

implicit def sizeOfContainer[
    T[_] : Foldable : OptionalLength,
    A : SizeOf : OptionalFixedSizeOf]: SizeOf[T[A]] = new SizeOf[T[A]] {
  def sizeOf(as: T[A]) = {

    // optionally calculate using Length + FixedSizeOf is possible
    val fixedLength = for {
      lengthOf <- implicitly[OptionalLength[T]]
      sizeOf <- implicitly[OptionalFixedSizeOf[A]]
    } yield lengthOf.length(as) * sizeOf.fixedSize

    // otherwise fall back to Foldable
    fixedLength.getOrElse { 
      val foldable = implicitly[Foldable[T]]
      val sizeOf = implicitly[SizeOf[A]]
      foldable.foldMap(as)(a => sizeOf.sizeOf(a))
    }
  }
}

Except this collides with fixedSizeOf() from earlier, which is still necessary.

Thanks for any help or perspective :-)

Answer 1

I eventually solved this using an ambiguity-based solution that doesn't require prioritizing using inheritance.

Here is my attempt at generalizing this.

We use the type Not[A] to construct negative type classes:

import scala.language.higherKinds

trait Not[A]

trait Monoid[_] // or import scalaz._, Scalaz._
type NotMonoid[A] = Not[Monoid[A]] 

trait Functor[_[_]] // or import scalaz._, Scalaz._
type NotFunctor[M[_]] = Not[Functor[M]]

...which can then be used as context bounds:

def foo[T: NotMonoid] = ...

We proceed by ensuring that every valid expression of Not[A] will gain at least one implicit instance.

implicit def notA[A, TC[_]] = new Not[TC[A]] {}

The instance is called 'notA' -- 'not' because if it is the only instance found for 'Not[TC[A]]' then the negative type class is found to apply; the 'A' is commonly appended for methods that deal with flat-shaped types (e.g. Int).

We now introduce an ambiguity to turn away cases where the undesired type class is applied:

implicit def notNotA[A : TC, TC[_]] = new Not[TC[A]] {}

This is almost exactly the same as 'NotA', except here we are only interested in types for which an instance of the type class specified by 'TC' exists in implicit scope. The instance is named 'notNotA', since by merely matching the implicit being looked up, it will create an ambiguity with 'notA', failing the implicit search (which is our goal).

Let's go over a usage example. We'll use the 'NotMonoid' negative type class from above:

implicitly[NotMonoid[java.io.File]] // succeeds
implicitly[NotMonoid[Int]] // fails

def showIfNotMonoid[A: NotMonoid](a: A) = a.toString

showIfNotMonoid(3) // fails, good!
showIfNotMonoid(scala.Console) // succeeds for anything that isn't a Monoid

So far so good! However, types shaped M[_] and type classes shaped TC[_[_]] aren't supported yet by the scheme above. Let's add implicits for them as well:

implicit def notM[M[_], TC[_[_]]] = new Not[TC[M]] {}
implicit def notNotM[M[_] : TC, TC[_[_]]] = new Not[TC[M]] {}

implicitly[NotFunctor[List]] // fails
implicitly[NotFunctor[Class]] // succeeds

Simple enough. Note that Scalaz has a workaround for the boilerplate resulting from dealing with several type shapes -- look for 'Unapply'. I haven't been able to make use of it for the basic case (type class of shape TC[_], such as Monoid), even though it worked on TC[_[_]] (e.g. Functor) like a charm, so this answer doesn't cover that.

If anybody's interested, here's everything needed in a single snippet:

import scala.language.higherKinds

trait Not[A]

object Not {
  implicit def notA[A, TC[_]] = new Not[TC[A]] {}
  implicit def notNotA[A : TC, TC[_]] = new Not[TC[A]] {}

  implicit def notM[M[_], TC[_[_]]] = new Not[TC[M]] {}
  implicit def notNotM[M[_] : TC, TC[_[_]]] = new Not[TC[M]] {}
}

import Not._

type NotNumeric[A] = Not[Numeric[A]]
implicitly[NotNumeric[String]] // succeeds
implicitly[NotNumeric[Int]] // fails

and the pseudo code I asked for in the question would look like so (actual code):

// NotFunctor[M[_]] declared above
def notFunctor[M[_] : NotFunctor](m: M[_]) = s"$m is not a functor"

Update: Similar technique applied to implicit conversions:

import scala.language.higherKinds

trait Not[A]

object Not {
  implicit def not[V[_], A](a: A) = new Not[V[A]] {}
  implicit def notNot[V[_], A <% V[A]](a: A) = new Not[V[A]] {}
}

We can now (e.g.) define a function that will only admit values if their types aren't viewable as Ordered:

def unordered[A <% Not[Ordered[A]]](a: A) = a