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 можно построить в таком виде (в какой либо категории функторов) - Y это скорее всего "примитив" такого же рода как например операция сложения двух чисел (если не выражать числа в какой либо лямбда-кодировке)

но теоретически конечно нужно тоже проверить :) вдруг чтото и получится ...

[maxim.livejournal.com]

Что получится? Типизировать Y? :-)

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

типизировать уже получилось :)
вопрос в выразимости Y в категории функторов - SKI и лямбды в функторах выражается без особых проблем как оказалось (SKI в Клейсли, лямбды непосредственно в виде функторов)
а вот с Y пока не ясно что делать в этом случае - ну кроме как просто лифтить в категорию полностью весь Y (да и то нужно еще понять как это лучше делать)

[maxim.livejournal.com]

А вижу, рекурсивные типы заюзаны

 static <A,B> Fun<A,B> Y(
                    final Fun<Fun<A,B>, Fun<A,B>> f) {
                return x -> f.apply(Y(f)).apply(x);
            }

Такое в Rust тоже можно написать.

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

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

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

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

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

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