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

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

}

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

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

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

Пример. Traversable

Когда у нас есть аппликативный функтор, у нас имеется что-то вроде моноида: есть относительный синглтон (не буду вдаваться в подробности), pure, и есть бинарная операция <*>; с помощью этих двух операций мы можем устраивать свёртку, скажем, списка... ну или дерева, если есть такая возможность, распараллелить, как в map/reduce. trait Traversable как раз обобщает список и дерево - по нему можно итерировать аппликативный функтор.

А именно,

// T будет траверсабельным, если определены:
trait Traversable[T[_]] {
  // для аппликативного функтора app и функции f обход структуры as
  def traverse[A, B, F[_]](app: Applicative[F])(f: A => F[B])(as: T[A]): F[T[B]]
  // и для, скажем, дерева аппликативов можно построить один аппликатив с деревом внутри
  def dist[B, F[_]](app: Applicative[F]) = traverse[F[B], B, F](app)(identity[F[B]]) _
}

Легко определить траверсабельность для списка:

implicit object TraversableList extends Traversable[List] {
  def cons[A](a: A)(as: List[A]): List[A] = a :: as

  def traverse[A, B, F[_]](app: Applicative[F])(f: A => F[B])(al: List[A]): F[List[B]] = {
    al match {
      case Nil => app.pure(List[B]())
      case head :: tail => app.applicable(app.lift(cons[B] _) <@> f(head)) <*> traverse[A, B, F](app)(f)(tail)
    }
  }
}

Тут как бы всё очевидно - если список пустой, то применяем pure, а иначе сканируем весь список, применяя последовательно <*>.

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

trait Tree[T]
case class Leaf[T](t: T) extends Tree[T]
def leaf[T](t: T): Tree[T] = Leaf(t)
case class Node[T](left: Tree[T], right: Tree[T]) extends Tree[T]
def node[T](left: Tree[T])(right: Tree[T]): Tree[T] = Node(left, right)

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

Вот как определяется траверс на таких деревьях:

implicit object TraversableTree extends Traversable[Tree] {

  def traverse[A, B, F[_]](app: Applicative[F])(f: A => F[B])(at: Tree[A]): F[Tree[B]] = at match {

    case Leaf(a) => app.lift(leaf[B]) <@> f(a)
    case Node(left, right) => {
      implicit def applicable[A, B](tf: F[A => B]) = app.applicable(tf)

      val traverse1: (Tree[A]) => F[Tree[B]] = traverse(app)(f)

      app.pure(node[B] _) <*> traverse1(left) <*> traverse1(right)
    }
  }
}

Обычное дело в Скале - пришлось ввести промежуточную переменную, traverse1, а то Скала в типах запутается. И так всё сложно.

Надо заметить, что не всякий функтор траверсабелен - например, функтор Env, попробуйте-ка его траверсировать с помощью Maybe - это было бы равносильно получению тотальной функции из частичной. Good luck.

Ну а теперь примеры траверса.

Список:

import TraversableList._

val distributor = dist[String, Set](AppSet)
val setOfLists = distributor(List(Set("a", "b"), Set("x", "y")))
setOfLists must_== Set(List("a", "x"), List("a", "y"), List("b", "x"), List("b", "y"))

Дерево:

import TraversableTree._

val distributor = dist[String, List](AppList)
val treeOfLists:Tree[List[String]] = Node(Leaf(List("a", "b")), Node(Leaf(List("x", "y", "z")), Leaf(List("1"))))
val listOfTrees = distributor(treeOfLists)
def tree(s: String) = Node(Leaf("" + s(0)), Node(Leaf("" + s(1)), Leaf("" + s(2))))
listOfTrees must_== List(tree("ax1"), tree("ay1"), tree("az1"), tree("bx1"), tree("by1"), tree("bz1"))

В следующей части - моноиды, и траверс с моноидами.