W algebrze, podobnie jak w codziennym tworzeniu pojęć, abstrakcje są tworzone przez grupowanie rzeczy według pewnych zasadniczych cech i pomijanie ich specyficznych innych cech. Abstrakcja jest ujednolicona pod jednym symbolem lub słowem oznaczającym podobieństwa. Mówimy, że abstrahujemy od różnic, ale to naprawdę oznacza, że integrujemy przez podobieństwa.
Rozważmy na przykład program, który bierze sumę liczb 1
, 2
oraz 3
:
val sumOfOneTwoThree = 1 + 2 + 3
Ten program nie jest zbyt interesujący, ponieważ nie jest zbyt abstrakcyjny. Możemy wyabstrahować liczby, które sumujemy, integrując wszystkie listy liczb pod jednym symbolem ns
:
def sumOf(ns: List[Int]) = ns.foldLeft(0)(_ + _)
I nie obchodzi nas też, że jest to lista. Lista jest konstruktorem określonego typu (pobiera typ i zwraca typ), ale możemy abstrahować od konstruktora typu, określając, jaką podstawową cechę chcemy (że można ją złożyć):
trait Foldable[F[_]] {
def foldl[A, B](as: F[A], z: B, f: (B, A) => B): B
}
def sumOf[F[_]](ns: F[Int])(implicit ff: Foldable[F]) =
ff.foldl(ns, 0, (x: Int, y: Int) => x + y)
Możemy mieć niejawne Foldable
instancje List
i każdą inną rzecz, którą możemy spasować.
implicit val listFoldable = new Foldable[List] {
def foldl[A, B](as: List[A], z: B, f: (B, A) => B) = as.foldLeft(z)(f)
}
val sumOfOneTwoThree = sumOf(List(1,2,3))
Co więcej, możemy abstrahować zarówno od operacji, jak i typu operandów:
trait Monoid[M] {
def zero: M
def add(m1: M, m2: M): M
}
trait Foldable[F[_]] {
def foldl[A, B](as: F[A], z: B, f: (B, A) => B): B
def foldMap[A, B](as: F[A], f: A => B)(implicit m: Monoid[B]): B =
foldl(as, m.zero, (b: B, a: A) => m.add(b, f(a)))
}
def mapReduce[F[_], A, B](as: F[A], f: A => B)
(implicit ff: Foldable[F], m: Monoid[B]) =
ff.foldMap(as, f)
Teraz mamy coś całkiem ogólnego. Metoda mapReduce
zwinie wszystkie F[A]
dane, które możemy udowodnić, że F
są składane i A
są monoidalne lub można je zmapować na jeden. Na przykład:
case class Sum(value: Int)
case class Product(value: Int)
implicit val sumMonoid = new Monoid[Sum] {
def zero = Sum(0)
def add(a: Sum, b: Sum) = Sum(a.value + b.value)
}
implicit val productMonoid = new Monoid[Product] {
def zero = Product(1)
def add(a: Product, b: Product) = Product(a.value * b.value)
}
val sumOf123 = mapReduce(List(1,2,3), Sum)
val productOf456 = mapReduce(List(4,5,6), Product)
Mamy wydobywane przez monoids i foldables.