Scalaz (31) - Free: 자유 데이터 구조 - 산식 과 알고리즘 에 대한 관심 분리

우 리 는 자유 데이터 구조 (Free Structure) 를 통 해 프로그램 에 대한 산식 과 알고리즘 분리 관심 (separation of concern) 을 실현 할 수 있다.산식 (Abstract Syntax Tree, AST) 은 연산 식 으로 프로그램 기능 에 대한 설명 입 니 다.알고리즘 은 프로그램의 구체 적 인 연산 방식 (Interpreter) 으로 산식 의 미 를 부여 한다.다음 에 우 리 는 먼저 하나의 예 로 산식, 알고리즘 이 무엇 인지 간단하게 설명 한다.
간단 한 표현 식 1 + 2 + 3 을 사용 합 니 다. 이 표현 식 은 산식 과 알고리즘 을 동시에 포함 합 니 다. 연산 식 은 a Op b Op c 이 고 알고리즘 은 Int 덧셈, a, b, c 는 Int 이 며 oP 는 Int + 입 니 다.그러면 우 리 는 그것 을 산식 과 산법 으로 분해 해 서 는 안 됩 니까?우 리 는 먼저 산식 을 유도 할 수 있다. Op (a, Op (b, c)).우 리 는 알고리즘 에서 Op 즉 a, b, c 에 대해 여러 가지 정 의 를 내 릴 수 있다. 즉, 이러한 정 의 를 통 해 우 리 는 산식 이 다른 의 미 를 부여 할 수 있다.이 예 는 산식, 알고리즘 이 분 리 된 전 과정 에 관심 을 가 질 수 있다. 우리 가 연산 하고 자 하 는 프로그램 을 추상 적 으로 묘사 하고 구체 적 인 연산 방식 을 정의 하면 분리 해서 진행 할 수 있다.
실제로 1 + 2 + 3 은 일종 의 모 노 이 드 조작 이 라 고 할 수 있다.그 중에서 Free Monoid 를 유도 할 수 있 는 지, 하나의 Monoid 자유 데이터 구조 가 Monoidal 작업 을 실현 하 는 산식, 알고리즘 분리 에 관심 을 가 질 수 있 는 지 살 펴 보 자.임의의 기본 형식 A 에 대한 Monoid 정 의 는 다음 과 같 습 니 다.
1. 이원 함수 append: (A, A) = > A
2. A 형식의 초기 값 (0 값) zero
Monoid 는 다음 과 같은 법칙 을 따라 야 합 니 다.
1. append 함수 의 연관 성 associativity: 임의의 A 유형의 x, y, z - append (x, append (y, z) = = append (x, y), z)
2. zero 의 동일 한 idenity law: 임의의 유형의 x - append (zero, x) = = append (x, zero)
위의 법칙 에 따 르 면 위의 표현 식 1 + 2 + 3 = = 1 + (2 + (3 + 0).그것 의 산식 은 다음 과 같다. append (x, append (y, append (z, zero))).그러면 우 리 는 이러한 Free Monoid 자유 데이터 구 조 를 얻 을 수 있 을 것 이다.

1 sealed trait FreeMonoid[+A] 2 final case object Zero extends FreeMonoid[Nothing] 3 final case class Append[A](l: A, r: FreeMonoid[A]) extends FreeMonoid[A]

1:: 2: 3: Nil > > List (1, 2, 3), A 가 Monoid 라면 List [A] 도 Monoid 이 고 List [A] 는 Free Monoid 자유 데이터 구조 입 니 다. 다음 시범 을 보 겠 습 니 다.

1 def listOp[A](l: List[A]): FreeMonoid[A] = l match { 2     case Nil => Zero 3     case h :: t => Append(h,listOp(t)) 4 }                                                 //> listOp: [A](l: List[A])Exercises.freestruct.FreeMonoid[A]
5 listOp(List(1,2,3))                               //> res0: Exercises.freestruct.FreeMonoid[Int] = Append(1,Append(2,Append(3,Zero 6                                                   //| )))

List 는 Free 입 니 다. Monoid, 그것 의 Nil = = Zero, a ++ b === Append(a,b)。
마찬가지 로 우 리 는 Monad 의 특성 조작 함수 에서 Free Monad 의 자유 데이터 구 조 를 유도 할 수 있다.우 리 는 다음 조작 함수 로 Monad M [] 을 구축 할 수 있다.
1、point: A => M[A]
2、join: M[M[A]] => M[A]
3、map: (M[A], A => B) => M[B]
(point + flatMap 조합 역시 Monad 를 구축 할 수 있 습 니 다)
Free Monad 는 형식 구축 기 Functor F [] 를 기반 으로 하 는 Free Monoid 이기 때문에 Free Monad 의 정 의 는 다음 과 같 아야 합 니 다.
sealed trait Free[F[_],A]
우 리 는 직접 point 를 case class 로 바 꿀 수 있다.
final case class Return[F[_],A](a: A) extends Free[F,A] 
join 의 입력 유형 은 F [F [A] 입 니 다. 우 리 는 free [F, A] 를 안에 넣 어야 합 니 다.
final case class Suspend[F[_],A](ffa: F[Free[F,A]) extends Free[F,A]
우 리 는 이제 Free Monad 의 자유 데이터 구조 정 의 를 다음 과 같이 추측 할 수 있다.

1 sealed trait Free[F[_], A] 2 final case class Return[F[_],A](a: A) extends Free[F,A] 3 final case class Suspend[F[_],A](ffa: F[Free[F,A]]) extends Free[F,A]

우 리 는 상기 구조 로 Monad 의 모든 특성 조작 함 수 를 실현 할 수 있다 는 것 을 증명 해 야 한다. 그러면 이 Free 는 Functor F 로 Monad 를 만 드 는 Monad 구조 기 이 고 가장 간단 한 구조의 Monad 구조 기, 즉 Free Monad 이다.

 1 import scalaz.Functor  2 final case class Return[F[_],A](a: A) extends Free[F,A]  3 final case class Suspend[F[_],A](ffa: F[Free[F,A]]) extends Free[F,A]  4 sealed trait Free[F[_],A] {  5   def point(a: A) = Return[F,A](a)  6   def flatMap[B](f: A => Free[F,B])(implicit F: Functor[F]): Free[F,B] =
 7     this match {  8       case Return(a) => f(a)  9       case Suspend(ffa) => Suspend[F,B](F.map(ffa)(fa => fa flatMap f)) 10  } 11   def map[B](f: A => B): Free[F,B] = flatMap(a => Return[F,B](f(a))) 12   def join(ffa: F[Free[F,A]]): Free[F,A] = Suspend[F,A](ffa) 13 
14 }

이 무료 자유 데이터 구 조 는 우리 가 point, flatMap, map, join 이라는 몇 개의 Monad 특성 조작 함 수 를 실현 하 는 것 을 충분히 지원 하기 때문에 무료 Monad 입 니 다.
Free 가 Free Monad 라면 Free [F, A] 의 F [A] 를 Program [Commands] 로 사용 할 수 있 습 니 다. 명령 집합 Commands 로 프로그램 을 독립 적 으로 설명 할 수 있 습 니 다. 최종 프로그램 프로그램 은 부작용 이 없 기 때문에 최대한 의 함수 조합 (function composition) 을 허용 합 니 다.. Program 에 대한 구체 적 인 연산 방법 은 독립 적 으로 분리 하여 실현 할 수 있 습 니 다. 우 리 는 다음 토론 에서 Free Monad 의 실제 응용 방식 인 AST 와 Interpreter 의 실현 과정 을 중점적으로 소개 할 것 입 니 다.