ScalaZ에서 FoldLeft 이해하기

Question

나는 ScalaZ에 관한 기사를 읽고 그것에 대해 질문이 있습니다. 이 article에서는 sum 함수를 일반화하여 합계 형식을 추상화합니다.

특성 모노 이드가 [A]로 정의된다

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

은 다음과 같습니다

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

예,이 꽤 분명하다. 여기 Monoid는 algebraic monoid structure에 해당합니다. 이제이 article에서 목록을 초월합니다. 우리는 다음과 같은 특성 정의이 수행하려면 : 나는 이론 카테고리의 전문가가 아니에요

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) 
} 

하지만에 실용적 펑과 같습니다 : 그래서 지금

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) 
    } 
} 

을 다음과 같이 우리는 sum 함수를 정의 할 수 있습니다 나를. 그 맞습니까? 범주 이론에 그러한 유사성을 제공 할 수 있습니까?

Answer 1

Applicative functor는 A => F[A] 및 F[A => B] => F[A] => F[B]의 두 가지 연산이있는 유형 클래스입니다. 언급 한 작업 중 해당 서명이 없습니다. FoldLeft은 Foldable과 같습니다. 그것은 다른 유형 클래스, 부모의 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 
} 

Type 클래스 Functor는 "컨테이너"F[_]을 의미하고이 컨테이너 내부 기능 f: A => B을 적용하는 방법을 알고있다. 유형 클래스 Applicative은이 컨테이너 안에 값 a: A을 포장하는 방법과 "기능"F[A => B]을 "값"F[A]에 적용하는 방법을 알고 있음을 의미합니다. Foldable은 이진 연산 A => B => B을 사용하고 시작 값이 B이고 결과가 B 인 방법을 사용하여 컨테이너를 접는 방법을 알고 있음을 의미합니다. Traversable은 모든 "노드"에서 적용 효과 A => F[B]을 실행하는 컨테이너를 트래버스하는 방법을 알고 있음을 의미합니다.