Type Classes as Object and Implicits

OMO10.scala

/** Type Classes as Object and Implicits
  *
  * @InProceedings{OMO10a,
  *   author =       {Bruno C. d. S. Oliveira and Adriaan Moors and Martin
  *                   Odersky},
  *   title =        {Type classes as objects and implicits},
  *   booktitle =    {Proceedings of the 25th Annual {ACM} {SIGPLAN}
  *                   Conference on Object-Oriented Programming, Systems,
  *                   Languages, and Applications, {OOPSLA} 2010, October
  *                   17-21, 2010, Reno/Tahoe, Nevada, {USA}},
  *   pages =        {341--360},
  *   year =         2010,
  *   url =          {http://doi.acm.org/10.1145/1869459.1869489},
  *   doi =          {10.1145/1869459.1869489},
  *   timestamp =    {Wed, 27 Oct 2010 13:53:08 +0200},
  *   biburl =
  *                   {http://dblp.uni-trier.de/rec/bib/conf/oopsla/OliveiraMO10},
  *   bibsource =    {dblp computer science bibliography, http://dblp.org}
  * }
  */
object OMO10a {

  /** Sort without Implicit.
    *
    * First, implicit prevent the cumbersome of passing explicit
    * constraint to generic algorithms. This is especially true when
    * many generic algorithms require multiple constraints on their
    * type parameters.
    *
    *
    * {{{
    * scala> import OMO10a.introWithoutImplicit._
    * scala> sort(List(2,3,1))(intOrd)
    * res0: List[Int] = List(1, 2, 3)
    * }}}
    */
  object introWithoutImplicit {
    def sort[T](xs: List[T])(ordT: Ord[T]): List[T] = xs match {
      case Nil => Nil
      case x :: xs => {
        val lesser = xs.filter(ordT.compare(_,x))
        val greater = xs.filter(!ordT.compare(_,x))

        sort(lesser)(ordT) ++ List(x) ++ sort(greater)(ordT)
      }
    }

    trait Ord[T] {
      def compare(a: T, b: T): Boolean
    }

    object intOrd extends Ord[Int] {
      override def compare(a: Int, b: Int) = a <= b
    }
  }

  /** Sort with Implicit prevents the cumbersome of passing constraint.
    *
    * {{{
    * scala> // ordT is no more required in sort:
    * scala> import OMO10a.introWithImplicit._
    * scala> sort(List(2,3,1))
    * res0: List[Int] = List(1, 2, 3)
    * }}}
    */
  object introWithImplicit {
    // Note: implicit in front of ordT
    def sort[T](xs: List[T])(implicit ordT: Ord[T]): List[T] = xs match {
      case Nil => Nil
      case x :: xs => {
        val lesser = xs.filter(ordT.compare(_,x))
        val greater = xs.filter(!ordT.compare(_,x))

        // ordT is no more required there
        sort(lesser) ++ List(x) ++ sort(greater)
      }
    }

    trait Ord[T] {
      def compare(a: T, b: T): Boolean
    }

    // Note: implicit in front of intOrd object
    implicit object intOrd extends Ord[Int] {
      override def compare(a: Int, b: Int) = a <= b
    }
  }

  /** Sort with Implicit let the programmer free to provide a constraint.
    *
    * Second, the programmer is free to provide an explicit argument.
    * This argument becomes part of the implicit scope so that implicit
    * argument is propagated naturally.
    *
    * {{{
    * scala> import OMO10a.implicitsInScala._
    * scala> implicit val out = System.out
    * scala> logTm("Does not compute!")
    * [Thu Jan 29 16:57:09 CET 2015] Does not compute!
    * scala> logTm("Does not compute!")(System.err)
    * Err: [Thu Jan 29 16:57:15 CET 2015] Does not compute!
    * }}}
    */
  object implicitsInScala {
    import java.io.PrintStream

    def logTm(msg: String)(implicit o: PrintStream): Unit =
      log("[" + new java.util.Date() + "] " + msg)

    def log(msg: String)(implicit o: PrintStream): Unit =
      o.println(msg)
   }

  /** Implicit argument list may either be omitter or supplied entirely.
    *
    * Problem is, when you want to pass multiple implicit arguments
    * and fix one of them, because implicit argument list may either
    * be omitted or supplied in its entirely. However there is a
    * simple idiom to encode a wild-card for an implicit argument.
    *
    * {{{
    * scala> import OMO10a.implicitsWildcard._
    * scala> implicit val out = System.out
    * scala> // When we want to fix a implicit parameter, the entire implicit
    * scala> // argument list must be supplied. Thus, without wild-card, if we
    * scala> // want to fix `prefix`, we also have to fix `output`.
    * scala> logPrefix("Does not compute!")(out, (new java.util.Date()).toString())
    * [Thu Jan 29 17:54:53 CET 2015] Does not compute!
    * scala> // With wildcard, we can omitting the value for the `output`,
    * scala> // while providing an explicit value for the `prefix`. Type
    * scala> // inference and implicit search will turn the `?` into
    * scala> // `?[PrintStream](out)`.
    * scala> logPrefix("Does not compute!")(?, (new java.util.Date()).toString())
    * [Thu Jan 29 17:54:53 CET 2015] Does not compute!
    * scala> // In scala, the `?[T]` methods is available as
    * scala> // scala.Predef.implicilty
    * scala> logPrefix("Does not compute!")(implicitly,
    * scala>                                (new java.util.Date()).toString())
    * [Thu Jan 29 17:54:53 CET 2015] Does not compute!
    * }}}
    */
  object implicitsWildcard {
    import java.io.PrintStream

    // LogTm generalization so that we can specify implicitly an
    // arbitrary output and an arbitrary prefix.
    def logPrefix(msg: String)(implicit
                               o: PrintStream,
                               prefix: String): Unit =
      log("[" + prefix + "] " + msg)

    def log(msg: String)(implicit o: PrintStream): Unit =
      o.println(msg)

    // Polymorphic method which look up an implicit value for type T
    // in the implicit scope.
    def ?[T](implicit w: T): T = w
  }


  /** Implicit is the missing link between type class and OO languages.
    *
    * Implicits provide the missing link for *type class programming*
    * to be convenient in *OO languages with generics*. They provide
    * the *type-driven selection mechanism* that was missing for type
    * class programming to be convenient in OO. Indeed, type-driven
    * selection mechanism offers a type-safe solution that propagates
    * constraint automatically. Here is another instance for Ord type
    * class and Tuple2 models.
    *
    * {{{
    * scala> import OMO10a.introWithImplicit._
    * scala> import OMO10a.implicitsIsMissingLink._
    * scala> sort(List((5, 6), (3, 4)))
    * res0: List[(Int, Int)] = List((3,4), (5,6))
    * }}}
    */
  object implicitsIsMissingLink {
    import introWithImplicit._

    implicit def pairOrd[A,B](implicit
                              ordA: Ord[A],
                              ordB: Ord[B]): Ord[(A,B)] = new Ord[(A,B)] {
      override def compare(x: (A, B), y: (A, B)) = ordA.compare(x._1, y._1) &&
        ordB.compare(x._2, y._2)
    }
  }

  // TODO: implicit overloading
  // object implicitOverloading { }

  /** Pimp My Library Pattern.
    *
    * After all, `ordA.compare(x._1, y._1)` is not idiomatic in OOP.
    * The pimp my library pattern use implicits to allow the more
    * natural `x._1.compare(y._1)` assuming that the type of `x._1`
    * doesn't define a `compare` method.
    *
    * {{{
    * scala> import OMO10a.pimpMyLibraryPattern._
    * scala> sort(List(2,3,1))
    * res0: List[Int] = List(1, 2, 3)
    * scala> sort(List((5, 6), (3, 4)))
    * res1: List[(Int, Int)] = List((3,4), (5,6))
    * }}}
    */
  object pimpMyLibraryPattern {
    import introWithImplicit._

    // Implicit values that have a *function type* act as *implicit
    // conversion*.
    trait Ordered[T] {
      def compare(o: T): Boolean
    }

    // The old way ; Requires an extra import:
    // import scala.language.implicitConversions
    // implicit def ord2Ordered[T](x: T)(implicit ordT: Ord[T]): Ordered[T] =
    //   new Ordered[T] {
    //     override def compare(o: T): Boolean = ordT.compare(x, o)
    //   }
    //
    // The good way ; Explanation: The Ord2Ordered is a *type*
    // specifically dedicated for the purpose of amending an existing
    // type `T` (and an `Ord[T]`) with extra methods. Whereas implicit
    // conversions allow for conversion from type `A` to a completely
    // unassociated `B` without `B` having been created specifically
    // for that purpose, i.e.: you cannot convert from type `A` to
    // type `B` with an implicit class `C` (assuming `C ≠ B`) but
    // instead only `A → C`. Whereas implicit conversion can convert
    // to any types and can be invoked with less visibility to the
    // programmer.
    implicit class Ord2Ordered[T](x: T)(implicit
                                        ordT: Ord[T]) extends Ordered[T] {
      override def compare(o: T): Boolean = ordT.compare(x, o)
    }

    // Here, `x._1.compare(y._1)` is converted to `ordA.compare(x._1,
    // y._1)` using ord2Ordered.
    implicit def pairOrd[A,B](implicit
                              ordA: Ord[A],
                              ordB: Ord[B]): Ord[(A,B)] = new Ord[(A,B)] {
      override def compare(x: (A, B), y: (A, B)) = x._1.compare(y._1) &&
        x._2.compare(y._2)
    }

    // The implicit conversion although works for the sort method:
    def sort[T](xs: List[T])(implicit ordT: Ord[T]): List[T] = xs match {
      case Nil => Nil
      case x :: xs => {
        val lesser = xs.filter(_.compare(x))
        val greater = xs.filter(!_.compare(x))

        sort(lesser) ++ List(x) ++ sort(greater)
      }
    }
  }

  /** Type-level computation.
    *
    * Combination of implicit search and dependent method types is an
    * interesting recipe for type-level computation. In the above
    * example, we generalize the `zipWith` function for two list
    * arguments into `n` list arguments.
    *
    * {{{
    * scala> import OMO10a.naryZipWith._
    * scala> def zipWith0 = zWith(Zero(), 0)
    * zipWith0: Stream[Int]
    * scala> def map[A,B](f: A => B) = zWith(Succ(Zero()), f)
    * map: [A, B](f: A => B) Stream[A] => Stream[B]
    * scala> def zipWith3[A,B,C,D](f: A => B => C => D)  =
    *          zWith(Succ(Succ(Succ(Zero()))), f)
    * zipWith3: [A, B, C, D](f: A => (B => (C => D)))
    *            Stream[A] => (Stream[B] => (Stream[C] => Stream[D]))
    * }}}
    */
  object naryZipWith {
    case class Zero()
    case class Succ[N](x: N)

    // Concept interface for zipWithN. `S` is the modeled type. `N` is
    // the arity of `S`.
    trait ZipWith[N,S] {
      // Type members that represents the type of ZipWith for `n` list
      // arguments. The type of ZipWith depends on `S`. For instance,
      // if `S` is an `Int`, then `ZipWithType` is `Stream[Int]`. if
      // `S` is a function `f: A => B => C`, then `ZipWithType` is
      // `Stream[A] => Stream[B] => Stream[C]`.
      type ZipWithType

      def manyApp: N => Stream[S] => ZipWithType
      def zipWith: N => S => ZipWithType =
        (n: N) => (f: S) => manyApp(n)(repeat(f))

      private def repeat[A](x: A): Stream[A] = x #:: repeat(x)
    }

    // Model for the base case.
    implicit def ZeroZW[S] = new ZipWith[Zero, S] {
      type ZipWithType = Stream[S]

      def manyApp = n => xs => xs
    }

    // Model for the inductive case.
    implicit def SuccZW[N,S,R](implicit
                               zw: ZipWith[N,R]) =
      new ZipWith[Succ[N], S => R] {
        type ZipWithType = Stream[S] => zw.ZipWithType

        def manyApp = n => xs => ss => n match {
          case Succ(i) => zw.manyApp(i)(zapp[S,R](xs,ss))
        }

        private def zapp[A,B](xs: Stream[A => B], ys: Stream[A]): Stream[B] =
          (xs, ys) match {
            case (f #:: fs, s #:: ss) => f(s) #:: zapp(fs, ss)
            case (_,_) => Stream.Empty
          }
      }

    // Method that calls zipWith for a function of arity `n`. That
    // method is the one that the developer should call to apply
    // zipWith. That method could be embedded in a "pimp-my-library
    // pattern" for an idiomatic usage.
    def zWith[N,S](n: N, s: S)(implicit
                               zw: ZipWith[N,S]): zw.ZipWithType =
      zw.zipWith(n)(s)
  }
}