Wild_exposed_as_a_GADT.scala

/* Modified version of https://gist.github.com/non/51b83d0abc929cc4f0b153accf2bf02f
 * to expose it's GADT's nature and provide the folding function.
 *
 * Should run out of the box with: amm <the_file>
 */

import $ivy.`org.typelevel:cats-core_2.12:1.6.0`
object demo {

import cats.{Applicative, Functor, Id, Semigroupal, Traverse}
import cats.arrow.FunctionK

/**
 * Represents the PolyType [A](F[A]) => G because it is still
 * not possible to write polytypes in Scala code. The suffix
 * 1_0 indicates F is of arity 1 while G is of arity 0.
 */
trait FunctionK_1_0[F[_], G] {
  def apply[A](x: F[A]): G
}

/**
 * Type-lifting operation to replace the wildcard type (i.e. _).
 *
 * In some cases we end up with code like: List[Option[_]]. This is
 * fine unless you later need to write code in terms of a particular
 * Option's type paramter (i.e. the underscore).
 *
 * With this code, you'd instead write: List[Wild[Option]]. Then, you
 * could say something like:
 *
 *     val ws: List[Wild[Option]] =
 *       List(Wild(Option(3)), Wild(Option("hi")), Wild(None))
 *     val w: Wild[Option] = xs.head
 *     val o: Option[w.Type] = w.value
 *     val e: w.Type = o.getOrElse(sys.error("!!!"))
 *
 * and you can now refer to the specific type of `e`. This is useful
 * when you may need to produce aligned values or have a "stable" way
 * of referring to an unknown type.
 */
sealed trait Wild[F[_]] extends Serializable {

  /**
   * This is the stable type used in place of an underscore.
   *
   * It relates a type to the F[Type] value we are holding.
   */
  type Type

  /**
   * This is the F[_] value we are holding.
   */
  def value: F[Type]

  /**
   * The fold function (universal mapping property of being an
   * initial object) associated this Generalized Algebraic Data Type (GADT)
   */
  final def fold[R](f: FunctionK_1_0[F,R]): R = f[Type](value)

  /**
   * Map Wild[F] into Wild[G] while preserving Type.
   *
   * For example:
   *
   *     val w0: Wild[List] = ...
   *     val f: FunctionK[List, Option] =
   *       new FunctionK[List, Option] {
   *         def apply[A](as: List[A]): Option[A] = as.headOption
   *       }
   *     val w1: Wild[Option] = w0.mapK(f)
   */
  final def mapK[G[_]](f: FunctionK[F, G]): Wild.Aux[G, Type] =
    Wild.typed(f(value))

  /**
   * Combine F[Type] and F[w.Type] into F[(Type, w.Type)] using an
   * implicit Semigroupal[F].
   *
   * For example:
   *
   *     import cats.implicits._
   *
   *     val w0: Wild[Option] = Wild(Some(8))
   *     val w1: Wild[Option] = Wild(Some(true))
   *     val w2: Wild[Option] = (w0 product w1)
   *
   *     println(w2) // Wild(Some((8, true)))
   */
  final def product(w: Wild[F])(implicit ev: Semigroupal[F]): Wild.Aux[F, (Type, w.Type)] =
    Wild.typed(ev.product(value, w.value))

  /**
   * Proxy `toString` to the underlying `value`.
   */
  final override def toString: String =
    s"Wild($value)"

  /**
   * Proxy `equals` to the underlying `value`.
   */
  final override def equals(that: Any): Boolean =
    that match {
      case w: Wild[_] => value == w.value
      case _          => false
    }

  /**
   * Proxy `hashCode` to the underlying `value`.
   */
  final override def hashCode: Int =
    value.hashCode
}

object Wild {

  /**
   * The only constructor of Wild[F] 
   */ 
  final case class Evidence[F[_],T](value: F[T]) extends Wild[F] {
    type Type = T
  }
  
  /**
   * When needed, we can use Wild.Aux[F, A] to refer to a Wild[F]
   * parameterized on a specific, known Type (i.e. A).
   */
  type Aux[F[_], A] = Wild[F] { type Type = A }

  /**
   * Construct a Wild[F] from an F[A] value.
   *
   * At the point of construction, the Type (A) is known. We expect to
   * later "forget" this type by combining various Wild[F] values
   * whose Type members are not known.
   *
   * Even though A is known, this method returns Wild[F] (i.e. it
   * erases the A type). If you want the A type "remembered" you can
   * use `typed` to get a `Wild.Aux[F, A]` back.
   */
  def apply[F[_], A](fa: F[A]): Wild[F] =
    typed(fa)

  /**
   * Construct a Wild.Aux[F, A] from an F[A] value.
   *
   * This method is similar to `apply` but it retains the A type in
   * its return value. Sometimes this is the desired behavior but
   * other times it will cause unification problems.
   */
  def typed[F[_], A](fa: F[A]): Wild.Aux[F, A] = Evidence[F,A](fa)

  /**
   * Support pattern-matching on Wild as if it was a case class.
   *
   * For example:
   *
   *     val w: Wild[Option] = Wild(Some(999))
   *     val Wild(o) = w
   *
   * This is a total pattern-match (it will never fail).
   */
  def unapply[F[_]](w: Wild[F]): Some[F[w.Type]] =
    Some(w.value)

  /**
   * If Wild is used with a pure `A` value, we can use `cats.Id` as
   * our `F[_]` type. The `Identity` alias (and friends) help make
   * this a bit more ergonomic.
   */
  type Identity = Wild[Id]

  /**
   * Construct an Identity value (Wild[Id]) from a given `a` value.
   */
  def identity[A](a: A): Identity = Wild[Id, A](a)

  /**
   * If `F` has a `Functor`, we can always push our unknown type
   * "through" a `Wild[F]` by wrapping our inner values in `Identity`.
   *
   * To see this, we can represent a List[Int] as either:
   *
   *     val before: Wild[List] = Wild(List(1, 2, 3))
   *     val after: List[Identity] = Wild.lower(before)
   *     // i.e. List(Wild.identity(1), Wild.identity(2), Wild.identity(3))
   *
   * However, we cannot go the other direction, since there is no one
   * type that can necessarily represents all the disparate values in
   * List[Identity].
   *
   *     val before: List[Identity] = List(Wild(1), Wild("two"))
   *     val after: Wild[List] = <impossible>
   */
  def lower[F[_]](w: Wild[F])(implicit ev: Functor[F]): F[Identity] =
    ev.map(w.value)(Wild.identity(_))

  /**
   * You can imagine Wild.sequence as doing two things:
   *
   *    (1) Pushing the "wildness" down (as per Wild.lower) to turn `F[Wild[G]]` into `F[G[Identity]]`
   *    (2) Turning `F[G[A]]` into `G[F[A]]` as per `sequence` provided by `cats.Traverse[F]`.
   *
   * This is equivalent to a single `traverse` as shown below.
   */
  def sequence[F[_], G[_]](fwg: F[Wild[G]])(implicit fev: Traverse[F],
                                            gev: Applicative[G]): G[F[Identity]] =
    fev.traverse(fwg) { (w: Wild[G]) =>
      lower(w)
    }
}
}