test.scala

test.scala

import scala.language.higherKinds

// The point of this exercise is to build up a data type isomorphic to List,
// using basic data types like Option and Tuple2. Along the way, we define
// functors, compositions of functors, fixed-points of functors, catamorphisms,
// and tagged types.
//
// I'm new to Scala, so there are probably prettier ways to do many of these
// things.
object Test {

  // We'll want to be able to partially-apply types. In my experience, this
  // Partial2 form is a little more readable than the type lambda form (at
  // for this case).
  type Partial2[T[_, _], B] = {
    type Apply[A] = T[B, A]
  }
  type Partial3[T[_, _, _], C, B] = {
    type Apply[A] = T[C, B, A]
  }

  // This is how we define functors.
  trait Functor[F[_]] {
    def fmap[A, B](fa: F[A])(f: A => B): F[B]
  }

  // And here are some implicit Functor instances for Option, Tuple2, and List.
  implicit def OptionFunctor: Functor[Option] = new Functor[Option] {
    def fmap[A, B](fa: Option[A])(f: A => B) = fa map f
  }
  implicit def Tuple2Functor[C]: Functor[Partial2[Tuple2, C]#Apply] =
    new Functor[Partial2[Tuple2, C]#Apply]
  {
    def fmap[A, B](fa: (C, A))(f: A => B) = (fa._1, f(fa._2))
  }
  implicit def ListFunctor: Functor[List] = new Functor[List] {
    def fmap[A, B](fa: List[A])(f: A => B) = fa map f
  }

  // Tagged types are similar to newtypes in Haskell: they can be erased at
  // compile time.
  type Tagged[U] = { type Tag = U }
  type @@[T, U] = T with Tagged[U]
  object Tag {
    @inline def apply[A, T](a: A) = a.asInstanceOf[A @@ T]
    @inline def unwrap[A, T](at: A @@ T) = at.asInstanceOf[A]
  }

  // And they allow us to tag two composed Functors as Composed.
  sealed trait Composed
  type Compose[F[_], G[_], A] = F[G[A]] @@ Composed

  // compose is just shorthand for tagging Functors as Composed.
  def compose[F[_]: Functor, G[_]: Functor, A](fga: F[G[A]]) =
    Tag[F[G[A]], Composed](fga)

  // And unCompose is just shorthand for untagging Functors tagged as Composed.
  def unCompose[F[_]: Functor, G[_]: Functor, A](fga: Compose[F, G, A]): F[G[A]] =
    Tag.unwrap(fga)

  // The composition of functors is a functor.
  implicit def ComposeFunctor[F[_]: Functor, G[_]: Functor]:
      Functor[Partial3[Compose, F, G]#Apply] =
    new Functor[Partial3[Compose, F, G]#Apply]
  {
    val F: Functor[F] = implicitly[Functor[F]]
    val G: Functor[G] = implicitly[Functor[G]]
    def fmap[A, B](fga: Compose[F, G, A])(f: A => B) =
      compose(F.fmap(fga)(G.fmap(_)(f)))(F, G)
  }

  // We can also take the fixed-point of a Functor. Once we have the fixed-
  // point, we can perform a catamorphism (generalized fold) on it with cata.
  class Fix[F[_]: Functor](val unFix: F[Fix[F]])(implicit val F: Functor[F]) {
    def cata[A](phi: F[A] => A): A = phi(F.fmap(unFix)(_.cata(phi)))
  }

  // fix is just shorthand for wrapping Functors in Fix.
  def fix[F[_]: Functor](f: F[Fix[F]]) = new Fix(f)

  // And unFix is just shorthand for unwrapping fixed Functors.
  def unFix[F[_]: Functor](f: Fix[F]) = f.unFix

  // Now we can build up our data type isomorphic to List...

  // MyList is the fixed-point of the composition of Option and Tuple2,
  type MyList[A] = Fix[Partial2[MyListF, A]#Apply]

  // where the composition of Option and Tuple2 has been broken out as a base
  // functor, MyListF (this makes the types easier to read/write).
  type MyListF[A, B] = Compose[Option, Partial2[Tuple2, A]#Apply, B]

  // Here, we define helper functions for constructing instances of MyList.
  def myNil[A]() = {
    val nil: MyListF[A, MyList[A]] =
      compose[Option, Partial2[Tuple2, A]#Apply, MyList[A]](None)
    fix[({type λ[α] = MyListF[A, α]})#λ](nil)(
      ComposeFunctor[Option, Partial2[Tuple2, A]#Apply])
  }
  def myCons[A](x: A, xs: MyList[A]) = {
    val cons: MyListF[A, MyList[A]] =
      compose[Option, Partial2[Tuple2, A]#Apply, MyList[A]](Some((x, xs)))
    fix[({type λ[α] = MyListF[A, α]})#λ](cons)(
      ComposeFunctor[Option, Partial2[Tuple2, A]#Apply])
  }

  // MyList is a Functor.
  implicit def MyListFunctor: Functor[MyList] = new Functor[MyList] {
    def fmap[A, B](myList: MyList[A])(f: A => B) = {
      def phi(fa: MyListF[A, MyList[B]]) =
        unCompose[Option, Partial2[Tuple2, A]#Apply, MyList[B]](fa) match
      {
        case None => myNil[B]
        case Some((x, xs)) => myCons[B](f(x), xs)
      }
      myList.cata(phi)
    }
  }

  // Now we'll show that our data type is isomorphic to List...

  // This is how we define isomorphisms. The intention is that you define to
  // for a pair of Isomorphisms, allowing from to be implicitly derived.
  trait Isomorphism[A, B] {
    def to(from: A): B
    def from[A, B](to: B)(implicit iso: Isomorphism[B, A]): A = iso.from(to)
  }

  // We can now show that MyList is isomorphic to List.
  implicit def MyListIsIsomorphicToList[A]: Isomorphism[MyList[A], List[A]] =
    new Isomorphism[MyList[A], List[A]]
  {
    def to(myList: MyList[A]) = {
      def phi(fa: MyListF[A, List[A]]) =
        unCompose[Option, Partial2[Tuple2, A]#Apply, List[A]](fa) match
      {
        case None => List[A]()
        case Some((x, xs)) => x :: xs
      }
      myList.cata(phi)
    }
  }
  implicit def ListIsIsomorphicToMyList[A]: Isomorphism[List[A], MyList[A]] =
    new Isomorphism[List[A], MyList[A]]
  {
    def to(list: List[A]) = list.foldRight(myNil[A])(myCons[A])
  }

}