апликативное программирование 8

[juan_gandhi]

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Весь нижеупомянутый код расположен на гитхабе у котят.

Пример аппликативного функтора: Вычислитель Выражений (монада Env)

В этом примере мы сможем вычислять значения выражений с переменными. Откуда берут значения переменные? Из окружающей среды;
эту среду зададим в виде Map[String, Int] - имена переменных будут строками, а значения целыми. Не убавляя общности.

    type Env = Map[String, Int] // хватило бы String=>Int, но для вящей демонстративности...

    type Environmental[X] = Env => X

    trait EnvFunctor extends Functor[Environmental] {
      override def f1[A, B](f: A => B) = (aa: Environmental[A]) => aa andThen f
    }

Здесь всё понятно, наверное. Теперь определим операции; трёх достаточно: выборка по имени, константа и сложение.

        val fetch = (varName: String) => (env: Env) => env(varName)
        val const = (value: Int) => (env: Env) => value
        val add = (i: Int) => (j: Int) => i + j

Я их тут нарочно определил как константы типа функция.
fetch - это константа (типа функция; можете считать референсом, как в Си); fetch("x") - результат
применения указанной функции к строке "x", т.е. функция, которая берёт Env и извлекает оттуда
значение по ключу "x"; fetch("x")(Map("a" -> 42, "x" -> "77", "y" -> 2012)) возвратит 77.

Предположив, что мы уже определили аппликативность (т.е. pure и <*>, напишем, как должна выглядеть
семантика наших выражений.

        trait Expr {
          def eval: Env => Int
        }

        case class Var(name: String) extends Expr {
          override def eval = fetch(name)
        }

        case class Val(i: Int) extends Expr {
          override def eval = const(i)
        }

        case class Add(p: Expr, q: Expr) extends Expr {
          override def eval =  pure(add) <*> p.eval <*> q.eval
        }

Для Var вычисление состоит в выборке, для Val вычисление состоит в возврате константы, а для сложения
нам как раз и нужна аппликативность. Мы не можем взять да пойти и сложить "значения" подвыражений - это не числа, это
функции, заданные на среде (Env); в Си пойнтеры складывать можно, а в Скале нельзя).

Ну и теперь надо поломать голову, как же определить аппликативность.

Начнём с комбинаторов (кто в армии служил лисп изучал, тот знает).

    implicit def K[A](a: A) = (env: Env) => a

    implicit def ski[Env, A, B](fe: Env => A => B) = new {
      val S = (ae: Env => A) => (env: Env) => fe(env)(ae(env))
    }

Здесь мы пишем implicit, чтобы в нужном контексте функция типа Env => A => B, превращалась в нечто, что способно применять комбинаторы.
Канонически комбинаторов три (S,K,I), но нам хватит двух, похоже.
Комбинатор K берёт значение и возвращает постоянную функцию на Env. а комбинатор S применяет функцию к значению.
В нашем же случае мы берём функцию, зависящую от среды и применяем к значению, зависящему от среды - получается другое значение, зависящее от среды.

Сейчас увидим, какая польза от комбинаторов.

    trait AppEnv extends EnvFunctor {
      def pure[A](a: A): Environmental[A] = K(a)

      implicit def applicable[A, B](fe: Environmental[A => B]) = new Applicable[A, B, Environmental] {
        def <*>(fa: Environmental[A]) = fe S fa // aka S(f, a)
      }
    }

Наши обе аппликативных операции выражаются через комбинаторы.
Тот факт, что функция S применяется инфиксно, формально никакого значения не имеет, но эстетически приятно.

      
object Expressions extends AppEnv {

  // эта функция выбирает значение переменной из среды
  val fetch = (varName: String) => (env: Env) => env(varName)
  // константа, не зависит от среды
  val const = (value: Int) => (env: Env) => value
  // сложение двух чисел
  val add = (i: Int) => (j: Int) => i + j

  // абстракция выражения
  trait Expr {
    def eval: Env => Int
  }

  // выражение, состоящее из переменной
  case class Var(name: String) extends Expr {
    override def eval = fetch(name)
  }

  // выражение, состоящее из константы
  case class Val(i: Int) extends Expr {
    override def eval = const(i)
  }

  // выражение, состоящее из суммы двух выражений
  case class Add(p: Expr, q: Expr) extends Expr {
    override def eval =  pure(add) <*> p.eval <*> q.eval
  }

  // пример выражения - это функция, её значение зависит от среды
  val expr = Add(Var("one"), Add(Var("three"), Val(11))).eval

  // а вот теперь мы её вычислим на среде
  expr (Map("one" -> 1, "two" -> 2, "three" -> 3)) must_== 15

}