import org.parboiled2._

object Simple extends App {

  trait LambdaCalculus[T] {
    def ref(n: String): T
    def lam(n: String, t: T): T
    def app(f: T, a: T): T
  }

  trait Expr[T] {
    def oper(a: T, f: String, b: T): T
    def parens(a: T): T
  }

  trait Literals[T] {
    def int(i: Int): T
  }

  trait Sym[T] extends LambdaCalculus[T]
    with Expr[T] with Literals[T]

  trait Ast {
    def apply[T: Sym]: T
  }

  trait SymAst extends Sym[Ast] {
    import Ast._

    def ref(n: String): Ast = Ref(n)
    def lam(n: String, t: Ast): Ast = Lam(n, t)
    def app(f: Ast, a: Ast): Ast = App(f, a)
    def oper(a: Ast, f: String, b: Ast): Ast = Oper(a, f, b)
    def parens(a: Ast): Ast = Parens(a)
    def int(i: Int): Ast = IntV(i)
  }
( Read more... )


  val main = "(x -> y -> z -> y * ( x + y * z))"
  val answer = parser(main)

  println(answer.map(ShowSym(_)))
  println(answer.map(SymVM(_, 1, 2, 10)))

  println(parser(main + " 1 2 10").map(x =>
    ShowSym(x) + " = " + SymVM(x)))

}

import org.parboiled2._

object Tagless extends App {

  trait Sym[F[_]] {
    def lit[A]: (String, A) => F[A]
    def app[A, B]: F[A => B] => F[A] => F[B]
    def lam[A, B]: String =>
      (F[A] => F[B]) => F[A => B]
  }

  type RunSym[A] = A
  object RunSym extends Sym[RunSym] {
    def lit[A] = (_, a) => a
    def app[A, B] = f => a => f(a)
    def lam[A, B] = s => f => f
  }

  type ShowSym[A] = String
  object ShowSym extends Sym[ShowSym] {
    def lit[A] = (s, _) => s
    def app[A, B] = f => a => s"$f($a)"
    def lam[A, B] = s => f => s"($s => ${f(s)})"
  }

  trait FSym[A] { def apply[F[_] : Sym]: F[A] }
  object FSym {
    def sym[F[_] : Sym] = implicitly[Sym[F]]
    def lit[A](s: String, a: A) = new FSym[A] {
      def apply[F[_] : Sym]: F[A] = sym.lit(s, a)
    }
    def lit[A](a: A) = new FSym[A] {
      def apply[F[_] : Sym]: F[A] = sym.lit(a.toString, a)
    }
    def app[A, B](f: FSym[A => B], a: FSym[A]) = new FSym[B] {
      def apply[F[_] : Sym]: F[B] = sym.app(f[F])(a[F])
    }
  }

  def showRunSym[A](f: FSym[A]) =
    s"${f(ShowSym)} = ${f(RunSym)}"

  object CalcSym {
    def int(x: String) = FSym.lit(x.toInt)
    def calc(f: FSym[Int => Int => Int]) =
      (x: FSym[Int], y: FSym[Int]) =>
        FSym.app(FSym.app(f, x), y)
    val PLUS = calc(FSym.lit("+", (x: Int) => x + _))
    val MINUS = calc(FSym.lit("-", (x: Int) => x - _))
    val MUL = calc(FSym.lit("*", (x: Int) => x * _))
    val DIV = calc(FSym.lit("-", (x: Int) => x / _))
  }

  class CalcSym(val input: ParserInput) extends Parser {
    import CalcSym._
    def parser = rule(Expr ~ EOI)
    def Expr: Rule1[FSym[Int]] =
      rule(Term ~ (Plus | Minus).+)
    def Term = rule(Factor ~ (Mul | Div).+)
    def Factor = rule(Number | Parens)
    def Plus = rule('+' ~ Term ~> PLUS)
    def Minus = rule('-' ~ Term ~> MINUS)
    def Mul = rule('*' ~ Factor ~> MUL)
    def Div = rule('/' ~ Factor ~> DIV)
    def Parens = rule(sp ~ '(' ~ sp ~ Expr ~ sp ~ ')' ~ sp)
    def Number = rule(sp ~ capture(Digits) ~ sp ~> (int _))
    def Digits = rule(CharPredicate.Digit.+)
    def sp = rule(zeroOrMore(' '))
  }

  val main = "(10 * 2 + 1) * 2"

  val answer = new CalcSym(main).parser.run()

  answer map showRunSym map println

}

// *(+(*(10)(2))(1))(2) = 42

object Tagless extends App {

  trait Sym[F[_]] {
    def lit[A]: (String, A) => F[A]
    def app[A, B]: F[A => B] => F[A] => F[B]
    def lam[A, B]: String => (F[A] => F[B]) => F[A => B]
  }

  object Sym {
    def apply[F[_] : Sym] = implicitly[Sym[F]]
    def lit[F[_] : Sym, A](s: String, a: A) = 
       Sym[F].lit(s, a)
    def lit[F[_] : Sym, A](a: A) = 
       Sym[F].lit(a.toString, a)
    def app[F[_] : Sym, A, B](f: F[A => B])
       (a: F[A]) = Sym[F].app(f)(a)
    def lam[F[_] : Sym, A, B](s: String)
       (f: (F[A] => F[B])) = Sym[F].lam(s)(f)
  }

  type RunSym[A] = A
  object RunSym extends Sym[RunSym] {
    override def lit[A]: (String, A) => RunSym[A] =
      (_, a) => a
    override def app[A, B]: (RunSym[(A) => B]) => 
      (RunSym[A]) => RunSym[B] = f => a => f(a)
    override def lam[A, B]: String => 
      ((RunSym[A]) => RunSym[B]) => RunSym[(A) => B] =
       s => f => f
  }

  type ShowSym[A] = String
  object ShowSym extends Sym[ShowSym] {
    override def lit[A]: (String, A) => ShowSym[A] = 
      (s, _) => s
    override def app[A, B]: (ShowSym[(A) => B]) => 
      (ShowSym[A]) => ShowSym[B] = f => a => s"$f($a)"
    override def lam[A, B]: String => 
      ((ShowSym[A]) => ShowSym[B]) => ShowSym[(A) => B] =
       s => f => s"($s => ${f(s)})"
  }

  import Sym._

  def PLUS[F[_] : Sym] = lit("+",
    (x: Int) => (y: Int) => x + y)

  def main[F[_] : Sym] = lam("x")((x: F[Int]) =>
    app(app(PLUS)(x))(x))

  def answer[F[_] : Sym] = app(main)(lit(21))

  println(s"${answer(ShowSym)} = ${answer(RunSym)}")

}

// (x => +(x)(x))(21) = 42

import cats._
import cats.data._
import cats.implicits._

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

object Sk extends App {
  val PLUS = ((_: Int) + (_: Int)).curried

  trait Lam_[->>[_, _]] {
    def app[E, A, B]: E ->> (A => B) => E ->> A => E ->> B

    def fun[A, B]: (A => B) => A ->> (A => B)

    def lam[A, B]: (A ->> A => A ->> B) => A ->> B
  }

  trait Lam[F[_]] extends Lam_[Kleisli[F, ?, ?]]

  implicit def lama[F[_] : Applicative]: Lam[F] =
    new Lam[F] {
      def AP[E] = Applicative[Kleisli[F, E, ?]]

      def app[E, A, B] = AP[E].ap[A, B]

      def fun[A, B] = AP[A].pure[A => B]

      def lam[A, B] = _ (Kleisli.ask[F, A])
    }

  object Lam {
    def apply[F[_] : Lam] = implicitly[Lam[F]]

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

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

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

  import Lam._

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

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

  answer[Id].apply(21)

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

}

  import cats._

  trait Sym[F[_]] {
    def lit[A]: A => F[A] // pure

    def app[A, B]: F[A => B] => F[A] => F[B] // ap

    def lam[A, B]: (F[A] => F[B]) => F[A => B] // coap?
  }

  implicit def symm[F[_] : Bimonad]: Sym[F] =
    new Sym[F] {

      val M = Bimonad[F]

      def lit[A] = M.pure[A]

      def app[A, B] = M.ap[A, B]

      def lam[A, B] = f =>
        M.pure[A => B](a =>
          M.extract(f(M.pure(a))))
    }

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

  def answer[F[_] : Sym]: F[Int => Int] = {
    val sym = implicitly[Sym[F]]
    import sym._
    lam(x => app(app(lit(PLUS))(x))(x))
  }