Понимание FoldLeft в ScalaZ

Question

Я читаю несколько статей о ScalaZ и есть вопрос о понимании этого. В этой статье мы обобщаем функцию суммы, чтобы абстрагироваться от типа, подлежащего суммированию.

def sum[T](xs: List[T])(implicit m: Monoid[T]) = //...

куда

Черта Monoid[A] определяется следующим образом:

trait Monoid[A] {
  def mappend(a1: A, a2: A): A
  def mzero: A
}

Да, это довольно ясно. Моноид здесь соответствует алгебраической структуре моноидов. Теперь в этой статье он абстрагируется от списков. Для этого мы определяем следующую черту:

trait FoldLeft[F[_]] {
  def foldLeft[A, B](xs: F[A], b: B, f: (B, A) => B): B
}
object FoldLeft {
  implicit val FoldLeftList: FoldLeft[List] = new FoldLeft[List] {
    def foldLeft[A, B](xs: List[A], b: B, f: (B, A) => B) = xs.foldLeft(b)(f)
  }
}

Итак, теперь мы можем определить функцию суммы следующим образом:

def sum[M[_]: FoldLeft, A: Monoid](xs: M[A]): A = {
  val m = implicitly[Monoid[A]]
  val fl = implicitly[FoldLeft[M]]
  fl.foldLeft(xs, m.mzero, m.mappend)
}

Я не эксперт в категории теории, но для меня это выглядит как Аппликативный функтор. Это верно? Можем ли мы обеспечить такое сходство с теорией категорий.

Answer 1

Аппликативный функтор - это класс типов с двумя операциями: A => F[A] а также F[A => B] => F[A] => F[B], Ни одна из упомянутых вами операций не имеет такой подписи. FoldLeft больше похоже на складной. Это класс другого типа, родительский для Traversable (иначе Traverse). А также Traversable связано с Applicative,

trait Functor[F[_]] {
  def fmap[A, B](f: A => B)(fa: F[A]): F[B]
}

trait Applicative[F[_]] extends Functor[F] {
  def pure[A](a: A): F[A]
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]
  override def fmap[A, B](f: A => B)(fa: F[A]): F[B] = ap(pure(f))(fa)
}

trait Foldable[T[_]] {
  def foldr[A, B](op: A => B => B)(seed: B)(ta: T[A]): B =
    (foldMap(op)(ta) _)(seed)
  def foldMap[A, M](f: A => M)(ta: T[A])(implicit monoid: Monoid[M]): M =
    foldr[A, M](a => m => monoid.append(f(a), m))(monoid.empty)(ta)
}

trait Traversable[T[_]] extends Functor[T] with Foldable[T] {
  def traverse[F[_]: Applicative, A, B](k: A => F[B])(ta: T[A]): F[T[B]] = 
    sequence[F, B](fmap[A, F[B]](k)(ta))
  def sequence[F[_]: Applicative, A](tfa: T[F[A]]): F[T[A]] = 
    traverse[F, F[A], A](fa => fa)(tfa)
  override def fmap[A, B](f: A => B)(ta: T[A]): T[B] = traverse[Id, A, B](f)(ta)
  override def foldr[A, B](op: A => B => B)(seed: B)(ta: T[A]): B =
    (traverse[Const[B => B]#λ, A, B](op)(ta) _)(seed)
  override def foldMap[A, M: Monoid](f: A => M)(ta: T[A]): M =
    traverse[Const[M]#λ, A, M](f)(ta)
}

type Id[A] = A

trait Const[C] {
  type λ[A] = C
}

Тип класс Functor означает, что у вас есть "контейнер" F[_] и вы знаете, как применить функцию f: A => B внутри этого контейнера. Тип класс Applicative означает, что вы знаете, как упаковать значение a: A внутри этого контейнера и как применить "функцию" F[A => B] в "значение" F[A], Foldable означает, что вы знаете, как сложить контейнер с помощью бинарной операции A => B => B и начальное значение B и получение результата B, Traversable означает, что вы знаете, как пройти свой контейнер, выполняя аппликативный эффект A => F[B] в каждом "узле".