Yoneda lemma explanation

yoneda.sc

// https://ru.wikipedia.org/wiki/%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%99%D0%BE%D0%BD%D0%B5%D0%B4%D1%8B

/*

Scala за 5 минут

int Plus(int Lhs, int Rhs) => lhs + rhs;                   def plus(lhs: Int, rhs: Int) = lhs + rhs;

Func<int, Int, Int> plus = (lhs, rhs) => lhs + rhs;        val plus: (Int, Int) => Int = (lhs, rhs) => lhs + rhs;

Func<int, int> Plus(int lhs) => (int rhs) => lhs + rhs;    def plus(lhs: Int)(rhs: Int) = lhs + rhs;

Func<int, Func<int, int>> plus = (lhs) => (rhs) 
                                          => lhs + rhs;    val plus: Int => Int => Int = lhs => rhs => lhs + rhs;
*/

trait Functor[F[_]] {
  def map[A, B](fa: F[A], f: A => B): F[B]
}

/*
interface Functor<F<>>
{
  F<B> Select<A, B>(F<A> Fa, Func<A, B> Fun);
}
*/

implicit class FunctorOps[F[_]: Functor, A](val fa: F[A]) {
  def map[B](f: A => B): F[B] = implicitly[Functor[F]].map(fa, f)
}

implicit class FunctorOps1[F[_], A](val fa: F[A]) {
  def map[B](f: A => B)(implicit fnctr: Functor[F]): F[B] = fnctr.map(fa, f)
}

/*
static class FunctorOps
{
  public static Select<F<>, A, B>(this F<A> Fa, Func<A, B> Fun, Functor<F<>> Instance) =>
    Instance.Select(Fa, Fun);
}
*/

/*
trait Yoneda[F[_], A] { self =>
  def apply[B](f: A => B): F[B]
}
*/

trait Yoneda[F[_], A] { self =>
  def apply[B](f: A => B): F[B]

  def map[B](f: A => B): Yoneda[F, B] =
    new Yoneda[F, B] {
      def apply[C](g: B => C): F[C] = self(f.andThen(g))
    }

  def run: F[A] = apply(a => a)
}

object Yoneda {
  def apply[F[_], A](fa: F[A])(implicit F: Functor[F]): Yoneda[F, A] =
    new Yoneda[F, A] {
      def apply[B](f: A => B): F[B] = F.map(fa, f)
    }
}

trait Coyoneda[F[_], A] { self =>
  type Pivot
  val fi: F[Pivot]
  def k: Pivot => A

  final def run(implicit F: Functor[F]): F[A] = F.map(fi, k)
}

object Coyoneda {
  type Aux[F[_], A, B] = Coyoneda[F, A] { type Pivot = B }

  def apply[F[_], A, B](fa: F[A])(k0: A => B): Aux[F, B, A] =
    new Coyoneda[F, B] {
      type Pivot = A
      val k = k0
      val fi = fa
    }
}

yoneda1.sc

import $ivy.`org.typelevel::cats-core:2.7.0`
import $ivy.`org.typelevel::cats-free:2.7.0`

import cats._
import cats.data.Cont
import cats.free.Yoneda
import cats.syntax.all._

sealed trait Tree[+T]
final case object Leaf extends Tree[Nothing]
final case class Node[T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T]

implicit val ft: Functor[Tree] = new Functor[Tree] {
  override def map[A, B](fa: Tree[A])(f: A => B): Tree[B] =
    fa match {
      case Leaf => Leaf
      case Node(value, left, right) => Node(f(value), map(left)(f), map(right)(f))
    }
}

def treeSize[T](tree: Tree[T]): Int = 
  tree match {
    case Leaf => 1
    case Node(_, lhs, rhs) => 1 + treeSize(lhs) + treeSize(rhs) 
  }

val sampleTree = Node("a", Leaf, Node("b", Leaf, Leaf))

println(treeSize(sampleTree))

def treeSize4[T](tree: Tree[T], start: Yoneda[Id, Int]): Yoneda[Id, Int] =
  tree match {
    case Leaf => start
    case Node(value, lhs, rhs) => 
      treeSize4(lhs, start).apply(nl =>
        treeSize4(rhs, start).apply(rl => start.map(_ + nl + rl)))
  }

println(treeSize4(sampleTree, Yoneda[Id, Int](1)).run)

def treeSize2[T, R](tree: Tree[T], f: Int => R): R =
    tree match {
      case Leaf => f(1)
      case Node(value, lhs, rhs) =>
        treeSize2(lhs, nl => 
          treeSize2(rhs, nr => f(1 + nl + nr)))
    }

println(treeSize2(sampleTree, identity _))