Весь нижеупомянутый код расположен на гитхабе у котят.
Пример. Моноид и Накопление Ошибок
Моноид, по-народному, это структура с ассоциативной бинарной операцией
+
и с нейтральным элементом относительно этой бинарной операции.Нейтральный элемент определяется как такой элемент
0
, что 0+a == a
и a+0 == a
для любого a
.Нейтральный элемент, разумеется, уникален: кабы их было два,
01
и 02
, то 01+02 == ...
ну вы поняли.Хотя операцию я тут и обозначил
+
, это ещё не значит, что она коммутативна.Да вы и сами знаете примеры некоммутативной операции, обозначаемой
+
. Ну хотя бы конкатенация двух строк.Структура с ассоциативной бинарной операцией без нейтрального элемента называется полугруппой. Моноид - это полугруппа с нейтральным элементом.
trait Semigroup[T] { def add(x: T, y: T): T // А является т.наз. фантомным параметром - нигде не используется, // и работает в качестве маркера case class Value[A](value: T) { def +(another: T): T = add(value, another) } implicit def value[A](x: T): Value[A] = Value(x) }
Это мы тут определили полугруппу, а также значения "из полугруппы", и для этих значений у нас определено сложение. Конкретный пример будет ниже.
Теперь моноид. Добавляем нейтральный элемент
_0
, а также внедрим аппликативность. В качестве аппликативного функтора будет выступать функтор константы. Для всякого значения из моноида - отдельный функтор. Аппликативность получается из моноидальных операций.trait Monoid[X] extends Semigroup[X] { val _0: X // Функтор, сопоставляющий постоянное значение (Value) object App extends ConstantFunctor[Value] with Applicative[Value] { // чистый ноль override def pure[A](a: A) = value[A](_0) // имеем два постоянных функтора, слияние состоит в сложении их значений override implicit def applicable[A, B](ff: Value[A => B]) = new Applicable[A, B, Value] { def <*>(fa: Value[A]) = Value(ff + fa.value) } } // вот и весь map/reduce: прошлись траверсом, сложили значения def accumulate[A,T[_]](traversable: Traversable[T])(eval: A => X)(ta: T[A]): X = { val evalAndWrap: A => Value[X] = eval andThen value traversable.traverse(App)(evalAndWrap)(ta).value } }
Здесь вызывает удивление, как это мы складываем ff и fa.value.
Дело в следующем. Мы имеем дело с постоянными функторами; и вот значение одного складываем со значением другого.
ff
, будучи типа Value
, имеет метод +
.Траверсы мы проходили в предыдущей части.
Теперь конкретные примеры моноидов.
object IntMonoid extends Monoid[Int] { val _0 = 0 def add(x: Int, y: Int) = x + y } object StringMonoid extends Monoid[String] { val _0 = "" def add(x: String, y: String) = x + y } trait ListMonoid[T] extends Monoid[List[T]] { val _0 = Nil def add(x: List[T], y: List[T]) = x ++ y }
Заметьте, что наше определение моноида уже даёт нам возможность суммировать списки, деревья, и всё, что можно обойти траверсом.
Вот нехитрый обход небольшого дерева из части 8:
import StringMonoid._ import TraversableTree._ def tree(s: String) = Node(Leaf("" + s(0)), Node(Leaf("" + s(1)), Leaf("" + s(2)))) val sut: Tree[String] = tree("abc") val collected: String = traverse(StringMonoid.App)((s: String) => "<<" + s + ">>")(sut).value collected must_== "<<a>><<b>><<c>>"
Теперь пример с накоплением ошибок. Скажем, у нас вычисления возвращают
Either
; в левой части Either
у нас какой-то специфический тип ошибок, которые можем накапливать в полугруппе (ну, скажем, это список исключений, или список сообщений об ошибках); из всего этого мы можем сделать аппликативный функтор (см. код ниже).trait AccumulatingErrors[Bad] { val errorLog: Semigroup[Bad] implicit def acc(err: Bad) = errorLog.value(err) type Maybe[T] = Either[Bad, T] object App extends Applicative[({type Maybe[A] = Either[Bad, A]})#Maybe] with RightEitherFunctor[Bad] { def pure[A](a: A):Either[Bad, A] = Right[Bad, A](a) implicit def applicable[A, B](maybeF: Either[Bad, A => B]) = { new Applicable[A, B, Maybe] { def <*>(maybeA: Maybe[A]) = (maybeF, maybeA) match { case (Left(badF), Left(badA)) => Left(badF + badA) case (Left(badF), _) => maybeF case (Right(f), Left(badA)) => maybeA case (Right(f), Right(a)) => Right(f(a)) } } } } }
Усложним задачу, и вместо списка ошибок будем строить дерево:
trait Oops case class Omg(what: String) extends Oops case class OiVei(first: Oops, second: Oops) extends Oops object Accumulator extends AccumulatingErrors[Oops] { val errorLog = new Semigroup[Oops] { def add(x: Oops, y: Oops) = OiVei(x, y) } } implicit def applicable[A, B](maybeF: Either[Oops, A => B]) = Accumulator.App.applicable(maybeF)
Ну и теперь определим хорошую функцию и плохую функцию, а также хорошую строку и плохую строку; хорошие возвращают "правые" значения, а плохие - "левые", с ошибкой внутри:
val goodFun = Right((s: String) => "<<" + s + ">>") val badFun = Left(Omg("snafu")) val goodString = Right("I am good") val badString = Left(Omg("I'm bad"))
И вот что у нас получится, если их поприменять друг к другу:
goodFun <*> goodString must_== Right("<<I am good>>") goodFun <*> badString must_== Left(Omg("I'm bad")) badFun <*> goodString must_== Left(Omg("snafu")) badFun <*> badString must_== Left(OiVei(Omg("snafu"), Omg("I'm bad")))
На этом наши изыскания в области МакБрайда и Патерсона закончены.
И вообще я закончил свои речи.
Хотел попоказывать sbt, но не нашел особо чего показывать - ну разве что найдутся добровольцы рассказать.
А так всё. Спасибо за внимание.
Questions?