Applicative functor is Lambda Calculus

[xacid]

  import cats._
  import cats.implicits._
  import scala.concurrent._
  import scala.concurrent.duration.Duration._
  import scala.concurrent.ExecutionContext.Implicits.global

  trait Lam[F[_]] {
    def lit[A](a: A): F[A]
    def op[A, B](f: A => B): F[A => B]
    def app[A, B](f: F[A => B])(a: F[A]): F[B]
  }

  object Lam {
    def apply[F[_] : Lam] = implicitly[Lam[F]]
    def lit[F[_] : Lam, A](a: A): F[A] = Lam[F].lit(a)
    def op[F[_] : Lam, A, B](f: A => B): F[A => B] =
      Lam[F].op(f)

    def app[F[_] : Lam, A, B](f: F[A => B])
                             (a: F[A]): F[B] =
      Lam[F].app(f)(a)

    def lam[F[_] : Lam, A, B](f: F[A] => F[B]) = f
  }

  implicit def applam[F[_] : Applicative]: Lam[F] =
    new Lam[F] {
      def lit[A](a: A): F[A] =
        Applicative[F].pure(a)

      def op[A, B](f: A => B): F[(A) => B] =
        Applicative[F].pure(f)

      def app[A, B](f: F[A => B])(a: F[A]): F[B] =
        Applicative[F].ap(f)(a)
    }

  val PLUS = ((_: Int) + (_: Int)).curried

  import Lam._

  def answer[F[_] : Lam] = lam((x: F[Int]) =>
    app(app(op(PLUS))(x))(x))

  def main[F[_] : Lam : Functor] =
    answer[F].andThen(_.map(println))

  main[Id].apply(21)

  Await.ready(main[Future].apply(Future(21)), Inf)

Comments

[http://users.livejournal.com/_xacid_/]

ну есть разные подходы к типизации Y но в данном конкретном случае типизация даже не рекурсивная (а вот реализация самая что ни на есть тупая рекурсивная :)

самый простой случай (как у меня выше вот)

Y:((a -> a) -> ( a -> a)) -> a -> a

но есть разумеется и с рекурсивными типами варианты

самое плохое другое - рекурсия не хвостовая - но по нормальному сделать хвостовую рекурсию достаточно сложно (если ее изначально нет в метаязыке) - только через некий вариант свободной монады (трамплин) в императивном цикле (это должно быть частью стандартного рантайма)