Instantly share code, notes, and snippets.

# alissapajer/gist:50c912d739346c1f00dd Last active Apr 1, 2016

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 }
Owner

### alissapajer commented Jun 19, 2014

 Proof of morphism composition preservation here: http://alissapajer.github.io/posts/2014-06-19-scalavariance.html
to join this conversation on GitHub. Already have an account? Sign in to comment