Skip to content

Instantly share code, notes, and snippets.

@alissapajer
Last active April 1, 2016 06:34
Show Gist options
  • Save alissapajer/50c912d739346c1f00dd to your computer and use it in GitHub Desktop.
Save alissapajer/50c912d739346c1f00dd to your computer and use it in GitHub Desktop.
Contravariant and Covariant Functors and Variance of Types over their Type Parameters
/**
* 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
}
@alissapajer
Copy link
Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment