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. Конкретные примеры аппликативных функторов
Должен извиниться, скальный вывод типов как-то мне не очень помогает, всё-таки не Хиндли-Милнер; поэтому ввожу и декларирую промежуточные переменные по мере необходимости. Если есть идеи как это упростить, буду рад.
![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
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)
}
}
То же самое мы можем повторить и с
Setobject 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 - мапредьюс на самом деле - опять с моноидом.
