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

[zeit-raffer.livejournal.com]

И SKI можно?

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

а SKI уже был :) только в категории Клейсли - но это наверное даже лучше

вобще вопрос понятный конечно - и попробовать для интереса конечно можно (я даже пробовал в предыдущей версии - но застопорился на S ) для проверки замкнутости и полноценности - но в практическом смысле мне кажется достаточно уже того что аппликативный функтор в категории Клейсли уже сам по себе представляет собой полный базис SKI

вобще тут еще много чего остается для дальнейшего исследования - я пока так быстро еще не успеваю все сразу проверить :) выкладываю результаты по мере их появления ... )

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

[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

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

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

[sassa-nf.livejournal.com]

ну да, Applicative по сути preserves exponent. F[B^A] → F[B]^F[A]

тут еще интересно: app ~ (.), потому что F[A=>B] `app` F[A] == F[A=>B] . F[()=>A] == F[()=>B]

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

а как определен (.) для F[_] ? :)

подозреваю что именно через <*> :)

[sassa-nf.livejournal.com]

ну для функтора известно как определен: F[(.)] = (.)

А для эндофунктора это одна и та же (.)

[clayrat.livejournal.com]

ну, это ж ровно настолько, насколько и аппликация вообще - частный случай композиции, нет?
F[A=>B] `ap` F[C=>A] == ?

[sassa-nf.livejournal.com]

да, почти. Здесь нужно как-то различить экспоненты и стрелки. Композиция стрелок есть, и функтор сохраняет их композицию. А что там с экспонентами? Экспонирование сохраняет композицию стрелок (в смысле eval экспоненты соответствующей композиции стрелок равно композиции eval экспонент стрелок). А функтор, сохраняющий композицию экспонент - апликативный.

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

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

[sassa-nf.livejournal.com]

я вообще-то не сварщик, а каску на стройке нашел.

Тут скорее вопрос к нотации. В теоркате F f - это отображение f в категорию. Однако, что такое F f в скале? Это fmap f? Или F[A=>B]? В первом случае f интерпретируется как стрелка (со встроенной в язык композицией), а во втором - как экспонента.

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

то есть мы с некоторой долей оптимизма можем просто сказать что экспонентой мы считаем стрелку поднятую в категорию функтора

[sassa-nf.livejournal.com]

Экспонентой мы считаем стрелку, когда она используется как объект. Функции высшего порядка как аргумент принимают экспоненты.

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

ага, ок. экспоненты это функции первого порядка

[sassa-nf.livejournal.com]

Лучше сказать, что экспоненты находятся в однозначном соответствии со стрелками.

(экспонента - это такой объект B^A, что для всех морфизмов f: A→B существует curry f: B^A такой, что коммутирует диаграмма eval . <1 × curry f> = f)

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

а такой вопрос - если у нас есть экспонента F[A] => F[B] какой формализм нам необходим (и достаточен) для создания стрелки к экспоненте F[A => B] ?

[sassa-nf.livejournal.com]

а такого не может быть, т.к. F[A]=>F[B] больше, чем F[A=>B].