Contravariant and Covariant Functors and Variance of Types over their Type Parameters

gistfile1.scala

/**
 * Exercises explaining covariant and contravariant functors.
 * 
 * Additionally exercises explaining variance of types over their type parameters.
 *
 * Implement the `???` functions. Are all implementable?
 */
  
trait Functors {
  /**
   * Covariant Functor Laws:
   * map(id) == id
   * map(f compose g) == map(f) compose map(g)
   */
  trait CovariantFunctor[F[_]] {
    def map[A, B](f: A => B): F[A] => F[B]
  }
  
  /**
   * Contravariant Functor Laws:
   * contramap(id) == id
   * contramap(f compose g) == contramap(g) compose contramap(f)
   */
  trait ContravariantFunctor[F[_]] {
    def contramap[A, B](f: A => B): F[B] => F[A]
  }

  type X
  
  // invariant over `A`
  trait Bar[A] {
    def bar(x: X): A
  }
  
  object CoBar extends CovariantFunctor[Bar] {
    def map[A, B](f: A => B): Bar[A] => Bar[B] = (barA: Bar[A]) => new Bar[B] {
      def bar(x: X): B = ???
    }
  }

  object ContraBar extends ContravariantFunctor[Bar] {
    def contramap[A, B](f: A => B): Bar[B] => Bar[A] = (barB: Bar[B]) => new Bar[A] {
      def bar(x: X): A = ???
    }
  }
  
  // invariant over `A`
  trait Foo[A] {
    def foo(a: A): X
  }
  
  object CoFoo extends CovariantFunctor[Foo] {
    def map[A, B](f: A => B): Foo[A] => Foo[B] = (fooA: Foo[A]) => new Foo[B] {
      def foo(b: B): X = ???
    }
  }

  object ContraFoo extends ContravariantFunctor[Foo] {
    def contramap[A, B](f: A => B): Foo[B] => Foo[A] = (fooB: Foo[B]) => new Foo[A] {
      def foo(a: A): X = ???
    }
  }

  // invariant over `A` and `B`
  trait FooBar[A, B] {
    def foobar(a: A): B
  }

  // covariant Hom functor
  class CoFooBar[C] extends CovariantFunctor[({type λ[α] = FooBar[C, α]})#λ] {
    def map[A, B](f: A => B): FooBar[C, A] => FooBar[C, B] = ???
  }

  // contravariant Hom functor
  class ContraFooBar[C] extends ContravariantFunctor[({type λ[α] = FooBar[α, C]})#λ] {
    def contramap[A, B](f: A => B): FooBar[B, C] => FooBar[A, C] = ???
  }

  /** 
   * contravariant over `A`
   * `fooV` must be defined on all of `A` and possibly more
   * a subtype of `FooV` defines a `fooV` defined on a supertype of `A`
   */
  trait FooV[-A] {
    def fooV(a: A): X
  }

  /**
   * covariant over `A`
   * `barV` must return an `A` or a subtype of `A`
   * a subtype of `BarV` defines a `barV` that returns a subtype of `A`
   */
  trait BarV[+A] {
    def barV(x: X): A
  }

  /**
   * contravariant over `A` and covariant over `B`
   * `foobarV` must be defined on at least `A` and return at most `B`
   * a subtype of `FooBarV` defines a `foobarV` that accepts a supertype of `A` and returns a subtype of `B`
   */
  trait FooBarV[-A, +B] {
    def foobarV(a: A): B
  }

  trait T
  trait S extends T  // S <: T

  /**
   * Scala tip:
   * for REPL playing purposes, you can make a `T` like this: `new T {}`
   */

  class P(foo: Foo[S])
  def p: P = ???

  class Q(bar: Bar[T])
  def q: Q = ???

  class PQ(foobar: FooBar[S, T])
  def pq: PQ = ???

  // FooV[T] <: FooV[S]
  class PV(fooV: FooV[S])
  def pv: PV = ???

  // BarV[S] <: BarV[T]
  class QV(barV: BarV[T])
  def qv: QV = ???

  // FooBarV[T, S] <: FooBarV[S, T]
  class PQV(foobarV: FooBarV[S, T])
  def pqv: PQV = ???
}

object Ack extends Functors {
  type X = Boolean  // this can be anything; useful to define when playing in REPL
}

Proof of morphism composition preservation here: http://alissapajer.github.io/posts/2014-06-19-scalavariance.html