팬 레 터 프로 그래 밍 (30) - 팬 레 터 IO: Free Monad - Monad 생산 라인

지난 절 에 우 리 는 Trampoline 을 소개 했다.스 택 넘 침 (StackOverflow) 오 류 를 해결 하기 위해 설계 되 었 습 니 다.Trampoline 유형 은 데이터 구조 입 니 다. 그의 디자인 방향 은 힙 으로 stack 을 바 꾸 는 것 입 니 다. 전통 적 인 재 귀 알고리즘 이 실 행 될 때 스 택 에 프로그램 상 태 를 저장 하고 Trampoline 으로 재 귀 알고리즘 을 할 때 프로그램 상 태 는 Trampoline 의 데이터 구조 에 저 장 됩 니 다.데이터 구 조 는 힙 에 있 기 때문에 힙 으로 Stack 을 바 꾸 는 효 과 를 실현 할 수 있다.이러한 데이터 구조 로 함수 호출 을 대체 하여 문 제 를 해결 하 는 방식 은 팬 레 터 프로 그래 밍 에 더욱 넓 은 발전 공간 을 제공 했다.
    우 리 는 IO 와 관련 된 모든 연산 이 스 택 넘 치 는 문제 에 직면 할 것 이라는 것 을 안다.IO 가 예상 치 못 한 데이터 양 과 반복 순환 작업 을 하기 때문이다.그래서 IO 알고리즘 디자인 도 Trampoline 과 같은 데이터 구 조 를 사용 합 니 다.또는 우 리 는 Trampoline 데이터 구조 와 알고리즘 을 이용 하여 IO 구성 요소 라 이브 러 리 를 설계 해 야 한다.이렇게 생각하면 우 리 는 반드시 Trampoline 에 대해 깊이 있 고 추상 적 이 어야 한다.Free Monad 는 Trampline 의 연장 입 니 다.Free Monad 를 소개 하기 전에 우 리 는 먼저 현실 적 인 예 에서 토론 을 전개 합 니 다.
만약 에 우리 가 은행 이체 함 수 를 작성 하려 고 한다 면 우 리 는 먼저 이 함수 의 디자인 (function signature) 을 유도 할 수 있 습 니 다.

1 def transfer(amount: Double, from: Account, to: Account, user: User, 2   context: Authorization with Logger with ErrorHandler with Storage): Unit

우선, 우 리 는 여기에서 매개 변수 주입 (parameter injection) 방식 을 사용 합 니 다. transfer 함수 입력 매개 변수 에 context object 를 주입 합 니 다.이 context object 에는 인증, 조작 추적, 오류 처리, 데이터 액세스 등 이 포함 되 어 있 습 니 다.이 건 전통 적 인 OOP 프로 그래 밍 모드 죠?팬 레 터 프로그래머 에 게 이 context object 를 통 해 일련의 조작 을 할 수 있 습 니 다.IO 조작 을 포함 하여 부작용 (side effect) 이 있 는 조작 을 할 수 있다 는 것 이다.그러면 이 함 수 는 함수 조합 (function composition) 을 실현 할 수 없습니다.transfer 함 수 는 팬 레 터 프로그래머 가 사용 해 야 할 함수 가 아 닙 니 다.
아마도 우 리 는 팬 레 터 프로 그래 밍 의 측면 에서 이 함 수 를 디자인 하려 고 시도 해 야 할 것 이다. 팬 레 터 프로 그래 밍 이 제창 하 는 탈바꿈 불 능 (immutability) 방식 으로 디자인 해 야 한다. 즉, 함수 호출 자 에 게 뭔 가 를 되 돌려 주 는 것 이다.
예 를 들 어 우 리 는 함수 호출 자 에 게 동작 을 설명 하 는 프로그램 을 되 돌려 줄 수 있 습 니 다. 명령 (instruction):

1 def transfer(amount: Double, from: Account, to: Account, user: User）： List[Instruction]

이 판본 은 틀림없이 범 함 판본 일 것 이다.하지만 Instruction 유형 에 상호작용 이 포함 된다 면 충분 하지 않 습 니 다.우 리 는 먼저 간단 한 상호작용 의 데이터 형식 을 살 펴 보 자.

1 trait Interact[A] //       2 //  ，    String    
3 case class Ask(prompt: String) extends Interact[String] 4 //  ，      
5 case class Tell(msg: String) extends Interact[Unit]

만약 우리 가 위의 생각 에 따라 명령 을 되 돌려 준다 면:

1  val prg = List(Ask("What's your first name?"), 2                  Ask("What's your last name?"), 3                  Tell("Hello ??? ???"))

이 프로그램 prg 는 결함 이 있 습 니 다. 상호작용 을 실현 할 수 없습니다.Ask 명령 을 임시 변수 에 저장 하면 목적 을 달성 할 수 있 을 것 같 습 니 다.그러면 우리 가 이 prg 를 다음 과 같이 바 꾸 면:

1 for { 2     x <- Ask("What's your first name?") 3     y <- Ask("What's your last name?") 4     _ <- Tell(s"Hello $y $x!") 5 } yield () 

이게 모 나 드 스타일 아니에요?원래 해결 방법 은 상호작용 유형 인 trait Interact [A] 를 Monad 로 바 꾸 면 된다.
그러나 인 터 랙 트 를 Monad 로 바 꾸 려 면 유닛 과 flatpap 두 함 수 를 실현 해 야 하 며 인 터 랙 트 trait 를 검사 하 는 것 은 불가능 하 다.
그럼 우 리 는 아래 의 노력 을 모 나 드 로 어떻게 바 꾸 느 냐 에 두 어야 한다.우리 가 이 명제 에서 프 리 모 나 드 를 언급 한 이상 모 나 드 생산 라인 이다.그러면 Free Monad 로 Interact 를 Monad 로 바 꿀 수 있 을까요?
우선 이 Free Monad 타 입 구 조 를 살 펴 보 겠 습 니 다.

1 trait Free[F[_],A] 2 case class Return[F[_],A](a: A) extends Free[F,A] 3 case class Bind[F[_],I,A](a: F[I], f: I => Free[F,A]) extends Free[F,A]

이 Free 결 과 는 Trampoline 과 너무 비슷 합 니 다.만약 Free 가 Monad 라면, 우 리 는 반드시 그것 의 flatMap 함 수 를 실현 해 야 한다.

 1 trait Free[F[_],A] {  2  def unit(a: A) = Return(a)  3  def flatMap[B](f: A => Free[F,B]): Free[F,B] = this match {  4        case Return(a) => f(a)  5 //   Trampoline FlatMap(FlatMap(b,g),f) == FlatMap(b, (x: Any) => FlatMap(g(x),f)) 
 6        case Bind(fa,g) => Bind(fa, (x: Any) => g(x) flatMap f)  7 //           。        8 // case Bind(fa,g) => Bind(fa, g andThen (_ flatMap f))
 9  } 10  def map[B](f: A => B): Free[F,B] = flatMap(a => Return(f(a))) 11 
12 } 13 case class Return[F[_],A](a: A) extends Free[F,A] 14 case class Bind[F[_],I,A](a: F[I], f: I => Free[F,A]) extends Free[F,A]

우 리 는 아래 의 lift 함수 로 Interact [A] 를 free [F, A] 로 승격 할 수 있다. ：

1 implicit def lift[F[_],A](fa: F[A]): Free[F,A] = Bind(fa, (a: A) => Return(a)) 2                                                   //> lift: [F[_], A](fa: F[A])ch13.ex6.Free[F,A]

lift 가 있 으 면 우 리 는 할 수 있 습 니 다. prg 는 Monad 로 승격 되 었 습 니 다.

 1 trait Interact[A] //        2 //  ，    String    
 3 case class Ask(prompt: String) extends Interact[String]  4 //  ，      
 5 case class Tell(msg: String) extends Interact[Unit]  6 
 7 implicit def lift[F[_],A](fa: F[A]): Free[F,A] = Bind(fa, (a: A) => Return(a))  8                                                   //> lift: [F[_], A](fa: F[A])ch13.ex6.Free[F,A]
 9 for { 10     x <- Ask("What's your first name?") 11     y <- Ask("What's your last name?") 12     _ <- Tell(s"Hello $y $x!") 13 } yield ()                                        //> res0: ch13.ex6.Free[ch13.ex6.Interact,Unit] = Bind(Ask(What's your first nam 14                                                   //| e?),<function1>)

 
이것 은 implicit scope 의 유형 전환 으로 인해 Interact 를 Free 로 승격 시 켰 고 Free 는 Monad 이기 때문에 우 리 는 for - comprehension 을 사용 할 수 있 습 니 다.
자, 이 프로그램 설명 이 끝 난 후에 어떻게 연산 해 야 합 니까?Free Monad 는 두 가지 기능 을 포함 하여 서로 관련 이 없 으 며 따로 고려 할 수 있 습 니 다.이른바 관심 분리 (separation of concern) 다.Free Monad 의 두 가지 기능 은 각각 Monad 와 Interpreter (번역 기) 이다.저 희 는 Monad 설명 프로그램 알고리즘 을 사용 하여 Interpreter 번역 프로그램 으로 특정한 운영 환경 에 대한 실행 가능 한 코드 를 만 듭 니 다.
Free Monad 의 Interpreter 는 알고리즘 과 연산 의 분리 고려 를 실현 했다.Interpreter 프로그램 연산 은 변환 함 수 를 통 해 이 루어 집 니 다.이 함 수 는 F [] 라 는 알고리즘 을 G [] 라 는 실행 가능 한 환경 을 위 한 Monad 실행 코드 로 해석 합 니 다.이러한 전환 은 바로 자연 변환 (Natural Transformation) 입 니 다. 함수 디자인 은 다음 과 같 습 니 다.

1 trait ~>[F[_],G[_]] { 2  def apply[A](fa: F[A]): G[A] 3 }

이 구축 함수 (constructor) 는 들 어 오 는 F [A] 를 G [A] 로 번역 한 것 이 분명 합 니 다.
현재 Interpreter 에서 알고리즘 을 실행 하 는 것 은 알고리즘 F [] 의 표현 식 을 일대일 로 G [] 변환 하 는 것 입 니 다.List 구조 에서 요 소 를 처리 하 는 방식 처럼 우 리 는 접 는 알고리즘 으로 F [] 구조 에서 표현 식 의 전환 을 실현 할 수 있 습 니 다.

1 def foldMap[G[_]: Monad](f: F ~> G): G[A] = this match { 2           case Return(a) => Monad[G].unit(a) 3           case Bind(b,g) => Monad[G].flatMap(f(b))(a => g(a).foldMap(f)) 4  }

우 리 는 foldpap 이 Free Monad F [] 의 표현 식 을 Monad G 상태 와 대응 하 는 것 을 보 았 다.빈 드 상 태 는 순환 적 으로 돌아 가 는 것 을 주의 하 세 요.
지금 우 리 는 가장 간단 한 번역 을 시도 해 볼 수 있다. F, Id 변환:

 1 ype Id[A] = A  2 implicit val idMonad: Monad[Id] = new Monad[Id] {  3     def unit[A](a: A) = a  4     def flatMap[A,B](fa: A)(f: A => B): B = f(fa)  5 }                                                 //> idMonad : ch13.ex6.Monad[ch13.ex6.Id] = ch13.ex6$$anonfun$main$1$$anon$1@2  6                                                   //| 530c12
 7 object Console extends (Interact ~> Id) {  8     def apply[A](i: Interact[A]): A = i match {  9         case Ask(prompt) => { 10  println(prompt) 11  readLine 12  } 13         case Tell(msg) => println(msg) 14  } 15 }

연산 위의 인 터 랙 트 프로그램: Id 가 아무런 효과 가 없 기 때문에 인 터 랙 트 에서 Id 로 전환 하 는 것 은 인 터 랙 트 표현 식 을 직접 연산 하 는 것 입 니 다.

1 val prg = for { 2     x <- Ask("What's your first name?") 3     y <- Ask("What's your last name?") 4     _ <- Tell(s"Hello $y $x!") 5 } yield ()                                        //> prg : ch13.ex6.Free[ch13.ex6.Interact,Unit] = Bind(Ask(What's your first n 6                                                   //| ame?),<function1>)
7 
8 prg.foldMap(Console)

아니면 우 리 는 좀 더 복잡 한 번역 을 시도 해 볼 수 있다.

 1 type Tester[A] = Map[String, String] => (List[String], A)  2 implicit val testerMonad = new Monad[Tester] {  3     def unit[A](a: A) = (_ => (List(),a))  4     def flatMap[A,B](ta: Tester[A])(f: A => Tester[B]): Tester[B] = {  5         m => {  6             val (l1,a) = ta(m)  7             val (l2,b) = f(a)(m)  8             (l1 ++ l2,b)  9  } 10  } 11 }                                                 //> testerMonad : ch13.ex6.Monad[ch13.ex6.Tester]{def unit[A](a: A): Map[Strin 12                                                   //| g,String] => (List[Nothing], A)} = ch13.ex6$$anonfun$main$1$$anon$2@5b464ce 13                                                   //| 8
14 object TestConsole extends (Interact ~> Tester) { 15     def apply[A](i: Interact[A]): Tester[A] = i match { 16       case Ask(prompt) => m => (List(), m(prompt)) 17       case Tell(msg) => _ => (List(msg),()) 18  } 19 }

이상 저 희 는 Interact 를 실행 하 는 상호작용 정 보 를 맵 [String, String] 구조 에 저장 합 니 다.여기 서 인 터 랙 트 에서 함수 맵 = > (List, A) 으로 전환 되 었 습 니 다.

1 val prg = for { 2     x <- Ask("What's your first name?") 3     y <- Ask("What's your last name?") 4     _ <- Tell(s"Hello $y $x!") 5 } yield ()                                        //> prg : ch13.ex6.Free[ch13.ex6.Interact,Unit] = Bind(Ask(What's your first n 6                                                   //| ame?),<function1>)
7 
8 prg.foldMap(TestConsole)

지난 절 에 우 리 는 Trampoline 에 대해 논 의 했 습 니 다. 팬 레 터 알고리즘 에서 불가피 한 스 택 넘 침 문 제 를 해결 하 는 것 이 주 된 목적 입 니 다. 만약 우리 가 Free Monad 로 IO 문 제 를 해결한다 면 스 택 넘 침 문 제 는 피 할 수 없습니다. 우 리 는 Free Monad 에서 Trampoline 유형 을 사용 하 는 것 을 고려 해 야 합 니 다. 그래 야 우 리 는 안심 하고 Free Monad 로 어떠한 종류의 Monad 를 생 성하 고 연산 할 수 있 습 니 다.스 택 넘 치 는 문 제 를 힙 으로 해결 합 니 다.