2012/06/25 06:19:14
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

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

Пример. Моноид и Накопление Ошибок



Моноид, по-народному, это структура с ассоциативной бинарной операцией + и с нейтральным элементом относительно этой бинарной операции.

Нейтральный элемент определяется как такой элемент 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?
60 посетителей, 7 комментариев, 2 ссылки, за 24 часа