Study notes for higher-kind types in Scala.

Resources

Background Techniques

Implicit Parameter

http://stackoverflow.com/questions/10375633/understanding-implicit-in-scala

The final parameter list on a method can be marked implicit, which means the values will be taken from the context in which they are called. If there is no implicit value of the right type in scope, it will not compile. Since the implicit value must resolve to a single value and to avoid clashes, it's a good idea to make the type specific to its purpose, e.g. don't require your methods to find an implicit Int!

// probably in a library
class Prefixer(val prefix: String)
def addPrefix(s: String)(implicit p: Prefixer) = p.prefix + s

// then probably in your application
implicit val myImplicitPrefixer = new Prefixer("***")
addPrefix("abc")  // returns "***abc"

// or use def if your right side value may need to inject extra type parameters in its typeclass definition.
implicit def findSomeValue[A](implicit a: Show[A]) = new Show[String] {
  // ....
}

// don't mixed the concept with implicit conversion
// implicit conversion
implicit def findSomeValue[A](a: Show[A]) = new Show[String] {
  // ....
}

Implicit Conversion

So if an type A is required and it finds a B, it will look for an implicit value of type signature B => A in scope

So the difference between your methods is that the one marked implicit will be inserted for you by the compiler when a Double is found but an Int is required.

An implicit conversion is an implicit value of unary function type A => B, or an implicit method that has in its first parameter section a single, non-implicit parameter. Examples:

implicit def doubleToInt(d: Double) = d.toInt
val x: Int = 42.0

//will work the same as

def doubleToInt(d: Double) = d.toInt
val x: Int = doubleToInt(42.0)

In the second we've inserted the conversion manually; in the first the compiler did the same automatically. The conversion is required because of the type annotation on the left hand side.

So implicit parameters are different mechanism than the implicit conversion.

Generics of a Higher Kind

The object-oriented term generics is the same concept as the first-order parametric polymorphism in functional programming. Due to type erasure feature in JVM, Scala hard to pass a type constrcutor as type parameter of another type constructor.
List is a type constructor, or type constructor function in Haskell. Scala present data(value) constructor via the case class or class defintion with subtype polymorphism.

trait Type[A] {}

case class SomeSubTypeAsDataConstructor[A]() extends Type[A]
def someMethod(a: List[Option[A]])

Since Haskell does not have subtype polymorphism as object-oriented supported, Haskell's data constructors are purely functions. To achieve similar subtype polymorphisms, consider put Void type in as type parameter of an data constructor, then by pattern matching, return Void.absurd to reduce unnecessary data constructor's value output. Make it similar to a subtype of the type constructor.

http://stackoverflow.com/questions/30623622/type-constructor-as-return-type

But note that with ADTs there are often alternatives that allow you achieve the same effect. In this case, one candidate technique would be to use the Void type in conjunction with Either:

-- | Extract the value a from Either Void a
-- | And make Left is never possible, make it similar to a subtype of Either with Right only.
extract :: Either Void a -> a
extract (Left x) = absurd x
extract (Right a) = a

Polymorphism

subtype polymorphism, Ad-hoc polymorphism, and parametric polymorphism.

Parametric polymorphism

Parametric polymorphism is a pattern in which polymorphic functions are written without mention of any specific type, and can thus apply a single abstract implementation to any number of types in a transparent way.

// type parameter F[_] introduce polymorphism.
trait Functor[F[_]] {
  def map[A, B](f: A => B): F[A] => F[B]
}

Subtype polymorphism

Subtype polymorphism is a pattern without introducing type parameters, its object-oriented way to desrcibe polymorphism. The methods that we’ve been calling monomorphic are only monomorphic in the sense of parametric polymorphism, and they can in fact be polymorphic in the traditional object-oriented way.

trait Base { def foo: Int }
class SubType1 extends Base { def foo = 3 }

// compile error, we cannot do overloading as Java.
class SubType2 extends Base { def foo: String = "Override" }

def subTypePolymorphism(t: Base) = t.foo
subTypePolymorphism(new SubType1)

Ad-hoc polymorphism

Leverage implicit conversion to implement for specific types.

case class FooDataConstructor(v: Int)

trait Base2[A] {
  def foo(a: A): A
}

object Base2 {
  implicit object Base2Foo extends Base2[FooDataConstructor] {
    def foo(a: FooDataConstructor): FooDataConstructor = a.copy(a.v * 5)
  }
}

object Run {
  // context bound is Base2
  def run[A: Base2](a: A): A = implicitly[Base2[A]].foo(a)
}

Run.run(FooDataConstructor(5))
// FooDataConstructor(25)

http://debasishg.blogspot.tw/2010/06/scala-implicits-type-classes-here-i.html

Type Members vs Type Oarameters

Note from Section 3.1, type members are less visible, and should not couple with the typeclass.

trait Builder[Container[X], T] {
  def +=(el: T): Unit
  def finalize(): Container[T]
}

trait Iterator[T] {
  def next(): T
  def hasNext: Boolean
  def foreach(op: T => Unit): Unit = while(hasNext) op(next())
}

// X is not neccessary though.
trait Buildable[Container[X]] {
  def build[T]: Builder[Container, T]
  
  def 
}

trait Iterable[T] {
  type Container[X] <: Iterable[X]
  
  def elements: Iterator[T]
  
  def mapTo[U, C[X]](f: T => U)(b: Buildable[C]): C[U] = {
    val buff = b.build[U]
    val elems = elements
    
    while(elems.hasNext()) {
      buff += f(elems.next)
    }
    
    buff.finalize()
  }
  
  def flatMapTo[U,C[X]](f: T⇒Iterable[U])(b: Buildable[C]): C[U] = {
    val buff = b.build[U]
    val elems = elements
    
    while(elems.hasNext){
      f(elems.next).elements.foreach{ el => buff += el }
    }
    buff.finalise()
  }
  
  def map[U](f: T => U)(b: Buildable[Container]): Container[U] = mapTo[U, Container](f)(b)
  def flatMap[U](f: T => Container[U])(b: Buildable[Container]): Container[U] = flatMmapTo[U, Container](f)(b)
}

Then we can have subtype polymorphism:

object ListBuildable extends Buildable[List]{
  def build[T]: Builder[List, T] = new ListBuffer[T] with Builder[List, T] {
    // += is inherited from ListBuffer (Scala
    standard library)
    def finalise(): List[T] = toList
  }
}

object OptionBuildable extends Buildable[Option] {
  def build[T]: Builder[Option, T] = new Builder[Option, T] {
    var res: Option[T] = None()
  
    def +=(el: T) = 
      if(res.isEmpty) res = Some(el)
      else throw new UnsupportedOperationException(">1 elements")
    
    def finalise(): Option[T] = res
  }
}

object List[T] extends Iterable[T] {
  type Container[X] = List[X]
  
  def elements: Iterator[T] = new Iterator[T] { /* ... */ }
}

val ages = List(Some(99), Some(56), None).flatMapTo[Int, List] {
  optBd => optBd.map { d => toYrs(d) }
} (OptionBuildable) (ListBuildable)

To make type member explicit, may write as:

Iterable[T]{type Container[X] = List[X]}
// or assign to any subtype of Iterable.

Kind

Consider kind soundness.

Variance

http://typelevel.org/blog/2016/02/04/variance-and-functors.html

Syntax

trait Seq[+A, C[+X]] { self: C[A] =>
  def lif[B >: A]: C[B] = this
}

self: C[A] => declare self as an alias of this.

def max[T <% Ord[T]](x: T, y: T): T
  = if (x <= y) y else x

View bound T <% Ord[T] is syntax sugar for an implicit parameter that converts the bounded type to its view bound, it can desugar as:

def max[T](x: T, y: T)(implicit conv: T => Ord[T]): T
  = if (x <= y) y else x

Or making it explicitly instead:

def max[T](x: T, y: T)(c: T => Ord[T]): T
  = if (x <= y) y else x

jamesyang124/higher-kind-scala.md