Pattern functors, algebras, folds, catas, free structures for free

[sir-wabbit]

trait Monoid[A] extends Typeclass {
  def empty: A
  def combine(a: A, b: A): A

  // Law syntax is not yet decided.
  def leftIdentity(a: A): Law  = combine(empty, a) is a
  def rightIdentity(a: A): Law = combine(a, empty) is a
  def associativity(a: A, b: A, c: A): Law = 
    combine(a, combine(b, c)) is combine(combine(a, b), c)
}
object Monoid {
  @free(Monoid) type Free[A]
}
// rewrite to:
object Monoid {
  sealed class Free[A]
  object Free {
    implicit def instance: Monoid[Free[A]] = ...
    def lift[A](a: A): Free[A] = ...
    def cata[A](f: A => B)(implicit B: Monoid[A]): B = ...
  }
}

Using the laws to simplify the structure seems a little bit tricky, but not impossible. One simple heuristic is to use any laws that reduce the total depth. In this case it's left and right identity laws.

Can we generate scott (Scott encoding, peeling one layer at a time) as well? i.e.

def scott[Z](f: Scott[Free[A], Z]): Z

trait Scott[A, Z] {
  def empty: Z
  def combine(a: A, b: A): Z

  // How to rewrite laws?
}

If Alg in @free(Alg) type Free[A] is not a typeclass, don't use implicit.