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

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

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

1. Детали

В предыдущих частях мы с изумлением видели, как красиво какой-нибудь список или Maybe, как брюки, превращаются в функтор, в монаду, в аппликативный функтор... причём, List чудесным образом мог превращаться сразу в два различных аппликативных функтора, первый обычный (когда сшивая два списка, получаем все возможные пары), а второй странный, когда сшиваем два списка вдоль, как замок молнию; для различения этот второй список, был назван ZipList - хотя он так-то, как параметризованный класс, ну ничем не отличается.
Дело в следующем. Нам надо бы расстаться с иллюзией, что как только мы имеем какой-нибудь параметризованный класс, так сразу у нас тут функтор. В общем случае это не так. Но в языках программирования мы имеем какую-то особую категорию, и т.наз. "Theorems for Free" обеспечивают нам функциональность, как только мы задали параметрический класс. То есть, таки достаточно задать отображение на типах.

Для меня тут лично много неясного (в частности, а что делать с контравариантными функторами), но я хочу оставить пока этот вопрос, и двигаться дальше. Но для задания аппликативного функтора явно недостаточно определить действие на типах и функциях. Например, для функтора List можно задать как минимум две версии аппликативности. Первая - берём произведение двух списков и возвращаем список всех пар; вторая, ZipList, - берём диагональ произведения двух списков, то, что в народе называют zip - такой аппликативный функтор называется ZipList

Но сначала давайте вернёмся и дадим формальные определения (на Скале).

2.Опять Функтор

2.1. Определение

trait Functor[T[_]] { self =>
  // mapping on objects of a category
  type f0[_] = T[_]

  // mapping on arrows of a category
  def f1[A, B](f: A => B): T[A] => T[B]

  // builds a composition of two functors
  def andThen[U[_]](u: Functor[U]) = new Functor[({type UT[X] = U[T[X]]})#UT] {
    def f1[A, B](f: A => B): (U[T[A]]) => U[T[B]] = u.f1(self.f1(f))
  }
}

Это функтор; в частности, композиция двух функторов - тоже функтор.

2.2. Примеры

  /**
   * Functorial features of List type
   */
  trait ListFunctor extends Functor[List] {
    override def f1[A, B](f: A => B) = (aa: List[A]) =>  aa map f
  }

  /**
   * Functorial features of Seq type
   */
  trait SeqFunctor extends Functor[Seq] {
    override def f1[A, B](f: A => B) = (aa: Seq[A]) => aa map f
  }

  /**
   * Functorial features of Set type (covariant version)
   */
  trait SetFunctor extends Functor[Set] {
    override def f1[A, B](f: A => B) = (sa: Set[A]) => sa map f
  }

  /**
   * Functorial features of Either[X,Y], for the second parameter
   */
  trait RightEitherFunctor[L] extends Functor[({type Maybe[A] = Either[L, A]})#Maybe] {
    def f1[A, B](f: A => B): Either[L, A] => Either[L, B] = _.right.map(f)
  }

Напомню, что Seq в Скале примерно соответствует джавному Iterable.

Последний пример - здесь тип RightEitherFunctor[L] параметризован - это означает, что для каждого L полученный Either[L, _] является функтором.

Более сложный пример - функтор Env:

  type E = Any => Int

  type Env[X] = E => X

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

В данном примере изображается зависимость от окружения. Вместо констант типа X мы начинаем манипулировать функциями, зависящими от окружения (в данном случае, для простоты, окружение возвращает какие-то целые числа.)

А, и мы тут приплели монаду Env - хотя никакой монадичности пока что не определяли, а только вот функториальность.

3. McBride and Paterson

Мне предложили пройтись по статье Conor McBride, Ross Paterson, "Applicative programming with effects". Я перепёр большую часть их хаскельного кода на Скалу, и в этой части продемонстрирую, как оно выглядит и что оно делает.

3.1. Аппликативный функтор (по МакБрайду-Патерсону)

trait Applicative[T[_]] extends Functor[T] { self =>
  def pure[A](a: A): T[A]

// below are additional enrichments, not exactly pertaining to Applicative
  def ap[A, B](fs: T[A => B]): (T[A] => T[B]) = (ta: T[A]) => fs <*> ta

  implicit def applicable[A, B](tf: T[A => B]): Applicable[A, B, T]

  trait Lifted[A, B, T[_]] { def <@>(ta: T[A]): T[B] }

  implicit def lift[A, B](fun: A => B) = new Lifted[A, B, T] {
    def <@>(ta: T[A]) = pure(fun) <*> ta
  }

  def andThen[U[_]](u: Applicative[U]) = new Applicative[({type UT[X] = U[T[X]]})#UT] {
    type UT[X] = U[T[X]]
    def f1[A, B](f: A => B): (U[T[A]]) => U[T[B]] = u.f1(self.f1(f))

    def pure[A](a: A) : U[T[A]] = u.pure(self.pure(a))

    implicit def applicable[A, B](utf: U[T[A => B]]) = {
      val uta2tb: U[(T[A]) => T[B]] = u.f1(self.ap[A, B])(utf)
      new Applicable[A, B, UT] {
        def <*>(uta: UT[A]) = u.applicable(uta2tb) <*> uta
      }
    }
  }
}

trait Applicable[A, B, T[_]] { def <*>(ta: T[A]): T[B] }

3.2. Конкретные примеры аппликативных функторов

Должен извиниться, скальный вывод типов как-то мне не очень помогает, всё-таки не Хиндли-Милнер; поэтому ввожу и декларирую промежуточные переменные по мере необходимости. Если есть идеи как это упростить, буду рад. sassa_nf постоянно подбрасывает идейки; огромное ему спасибо.

object AppList extends ListFunctor with Applicative[List] {
  override def pure[A](a: A) = List(a)

  override implicit def applicable[A, B](lf: List[A => B]): Applicable[A, B, List] = {
    new Applicable[A, B, List] {
      def <*>(as: List[A]) = (for (f <- lf; a <- as) yield f(a)).toList
    }
  }
}

Здесь мы построили аппликативный функтор для списка, с операцией <*>, строящей декартово произведение списков; ну а остальное оттуда следует.

Вот этот тест иллюстрирует:

    "ApplicativeList" should {
      "combine two lists" in {
        import applicative.All.AppList._
        def pp(i: Int) = (j: Int) => i + j * j

        val combinations:List[Int] = ap(List(pp(1), pp(2)))(List(10, 20, 30))
        combinations must_== List(101, 401, 901, 102, 402, 902)
      }
    }

То же самое мы можем повторить и с Set

object AppSet extends SetFunctor with Applicative[Set] {
  override def pure[A](a: A) = Set(a)

  override implicit def applicable[A, B](ff: Set[A => B]) = {
    val sf: Set[A => B] = ff
    new Applicable[A, B, Set] {
      def <*>(fa: Set[A]) = (for (f <- sf; a <- fa) yield f(a)).toSet
    }
  }
}

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

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

object AppZip extends SeqFunctor with Applicative[Seq] {

  override def pure[A](a: A): Seq[A] = Stream.continually(a) // повторяем пока кому-нибудь не надоест

  implicit def applicable[A, B](ff: Seq[A => B]) = {
    new Applicable[A, B, Seq] {
      def <*>(az: Seq[A]) = ff zip az map ({ case (f: (A => B), a: A) => f(a) }) // в Скале уже есть зип; применим его
    }
  }
}

Смотрите, когда мы зипуем два списка, то полученный список прекращается по исчерпанию любой из компонент. Поэтому для того, чтобы, к примеру, одну и ту же функцию применить к списку (или наоборот, список функций к одному значению), мы вместо синглтона берём бесконечную последовтельность. Если б мы использовали списки, тут бы наш код и завис - чтоб зазиповать, он бы возжелал перечислить весь список. В Хаскеле списки ленивы. А в Скале ленивы потоки (Stream).

"ZipList" should {
  import All.AppZip._

  "be able to zip functions with values" in {

    def prepend(prefix: String) = (s: String) => prefix + " " + s
    val result = (List(prepend("a"), prepend("the")) <*> List("quick brown fox jumps over ", "lazy dog "))
    result must_== List("a quick brown fox jumps over ", "the lazy dog ")
  }
}

Вот более сложный пример - транспонирование матриц. (Я лично не приветствую идею представлять матрицу в виде списка списков, но это просто пример...
Так как zip у нас применяется к последовательностям, то на самом деле мы транспонируем последовательность списков.

"be able to transpose a matrix" in {

  trait matrices[A] { // матрицы с абстрактными элементами
    type matrix = Seq[Seq[A]]

    val glue: Seq[A => List[A] => List[A]] = pure(cons _) // функция, конкатенирующая элемент и список, применяется к последовательности

    def transpose(m: matrix): matrix = if (m.isEmpty) Nil else transposeNonempty(m) // приходится различать пустую и непустую, потому что размерность не указывать

    def transposeNonempty(m: matrix): matrix = { // нетривиальная часть
      m match {
        case Nil => pure(Nil) // это на случай, когда непустой вектор склеиваем с пустой матрицей
        case row :: rows => { // типичный случай - применим клей к row и остатку
          glue <*> row <*> transposeNonempty(rows)
        }
      }
    }
  }

  object m extends matrices[Int]
  import m._

  val m0x0: m.matrix = transpose(List[List[Int]]()).toList
  m0x0 must_== List() // мы не можем даже выразить m0x1

  val m0x1: m.matrix = transpose(List(List[Int]()))
  m0x1 must_== List()

  val m2x1: m.matrix = transpose(List(List(1, 2)))
  m2x1 must_== List(List(1), List(2))

  val m1x2: m.matrix = transpose(List(List(1), List(2))).toList
  m1x2 must_== List(List(1,2))

  val m2x2 = transpose(List(List(11, 12), List(21, 22))).take(12).toList
  m2x2 must_== List(List(11, 21), List(12, 22))
}

Этого, пожалуй, хватит на этот раз; в следующей части будет аппликативный функтор, вычисляющий арифметические выражения - не с константами, а с функциями (зависимость от "среды").
Затем моноид и "накопление сообщений об ошибках" (накапливаем в моноиде) и обход... ну не дерева, а Traversable - мапредьюс на самом деле - опять с моноидом.

микродыбр

Короче, вчера вылетел в час дня из СФ, прилетел в час ночи в Атланту; а в Цинциннати уже сегодня утром.

9 часов в самолёте, половина на поле. Хорошо у меня были орехи и морковка. Но лаптоп и телефон разрядились. Пришлось читать книжку про решетки. Херня эти ваши соответствия Галуа, детский сад. Всё из категорий следует элементарно.

Почитаю ещё подробней про "темпоральную логику", но сдаётся мне...

Зато ночью в Атланте наконец дописал часть 7 и 8 (почти).

Народ мне в Атланте понравился, в аэропорту. Но интернета там нет (не нашел). Еда очень дешевая.

Вообще, дельтой буду летать. Как-то всё очень мило.