Scalaz (35) - Free: 연산 - Trampoline, NO to StackOverflow 오류

앞의 몇 차례 토론 에서 우 리 는 Free 가 Monad 를 만 드 는 가장 기본 적 인 구조 라 고 소개 했다.그것 의 원 리 는 프로그램 (AST) 의 일련의 연산 명령 (ADT) 을 데이터 구조 로 바 꾸 어 메모리 에 저장 하 는 것 이다. 이 과정 은 독립 된 기능 설명 과정 이다.그리고 또 다른 독립 연산 과정의 Interpreter 는 (traverse) AST 구 조 를 옮 겨 다 니 며 구조 에 있 는 연산 명령 을 읽 고 실제 명령 을 실행 합 니 다.여기 서 중점 은 일련의 연산 구조 화 (reify) 를 지연 시 키 는 것 이다. 구체 적 인 실현 방식 은 Monad 의 연속 연산 방법 인 flatMap 을 Suspend 구조 (case class) 로 전환 시 키 고 연산 과정 을 생 성 (construct) Suspend 과정 으로 전환 하 는 것 이다.flatMap 의 표현 형식 은 다음 과 같 습 니 다: flatMap (a = > flatMap (b = > flatMap (c = >...)))). 이것 은 뚜렷 한 재 귀 알고리즘 으로 스 택 넘 침 이상 (StackOverflow Exception) 이 발생 하기 쉬 우 며 프로그램의 안전 운행 을 보장 할 수 없습니다. 효과적으로 해결 하지 못 하면 FP 프로 그래 밍 이 불가능 합 니 다.Free 는 바로 이 문 제 를 해결 하 는 효과 적 인 방법 이다. 왜냐하면 Monad 의 귀속 알고리즘 인 flatMap 을 데이터 구조의 실례 를 만 드 는 과정 으로 바 꾸 었 기 때문이다.Suspend 를 만 들 때마다 연산 을 즉시 완성 합 니 다.우 리 는 먼저 예 를 들 어 Monad flatMap 의 재 귀 알고리즘 문 제 를 증명 합 니 다.

 1 ef zipIndex[A](xa: List[A]): List[(Int,A)] =
 2  xa.foldLeft(State.state[Int,List[(Int,A)]](List()))(  3     (acc,a) => for {  4       xn <- acc  5       s <- get[Int]  6       _ <- put[Int](s+1)  7     } yield ((s,a) :: xn)  8   ).eval(1).reverse                               //> zipIndex: [A](xa: List[A])List[(Int, A)]
 9 
10 zipIndex(1 |-> 10)                                //> res6: List[(Int, Int)] = List((1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (7,7), (8,8), (9,9), (10,10))
11 zipIndex(1 |-> 10000)                             //> java.lang.StackOverflowError

이 예 에서 우 리 는 State Monad 를 사용 했다.우 리 는 for - comprehension 이 바로 flatMap 체인 이 고 재 귀 알고리즘 이라는 것 을 알 기 때문에 zipIndex 가 큰 List 를 대상 으로 할 때 StackOverflow Error 가 발생 했다.
우 리 는 Trampoline 을 사용 하면 힙 을 stack 으로 바 꾸 고 데이터 구 조 를 옮 겨 다 니 며 재 귀 연산 을 대체 하여 운행 안전 을 실현 할 수 있다 고 언급 한 적 이 있다.그럼 트 램 폴 린 이 뭐 죠?

1 sealed trait Trampoline[+A] 2 case class Done[A](a: A) extends Trampoline[A] 3 case class More[A](k: () => Trampoline[A]) extends Trampoline[A]

Trampoline 은 일종 의 데이터 구조 다.이 는 두 가지 상태 가 있 습 니 다. Done (a: A) 대표 구조 에 A 값 이 저장 되 어 있 습 니 다. More (k: () = > Trampoline [A] 대표 구조 에 저 장 된 것 은 Function 0 함수 이 고 연산 Trampoline [A] 입 니 다.
우 리 는 먼저 재 귀 알고리즘 예 를 시험 해 보 자.

 1 def isEven(xa: List[Int]): Boolean =
 2  xa match {  3     case Nil => true
 4     case h :: t => isOdd(t)  5   }                                               //> isEven: (xa: List[Int])Boolean
 6 def isOdd(xa: List[Int]): Boolean =
 7  xa match {  8     case Nil => false
 9     case h :: t => isEven(t) 10   }                                               //> isOdd: (xa: List[Int])Boolean
11 
12 isOdd(0 |-> 100)                                  //> res0: Boolean = true
13 isEven(0 |-> 10000)                               //> java.lang.StackOverflowError

isEven 과 isOdd 라 는 두 함수 가 서로 재 귀적 으로 호출 되 는 것 을 볼 수 있 습 니 다. 마지막 으로 큰 List 를 사용 하면 StackOverflow Error 가 발생 합 니 다.
함수 isEven 과 isOdd 의 반환 구조 유형 을 다시 조정 합 니 다. Boolean 에서 Trampoline 으로 바 꾸 면 결과 값 을 되 돌려 주 는 것 에서 데이터 구 조 를 되 돌려 주 는 것 을 의미 합 니 다.

 1 def even(xa: List[Int]): Trampoline[Boolean] =
 2  xa match {  3     case Nil => Done(true)  4     case h :: t => More(() => odd(t))  5   }                                               //> even: (xa: List[Int])Exercises.trampoline.Trampoline[Boolean]
 6 def odd(xa:  List[Int]): Trampoline[Boolean] =
 7  xa match {  8     case Nil => Done(false)  9     case h :: t => More(() => even(t)) 10   }                                               //> odd: (xa: List[Int])Exercises.trampoline.Trampoline[Boolean]
11   
12 even(1 |-> 123001)                                //> res0: Exercises.trampoline.Trampoline[Boolean] = More(<function0>)

현재 우 리 는 힙 에 123001 개의 요 소 를 저장 한 데이터 구조 More (< function0 >) 를 얻 었 다.이것 은 메모리 힙 에 저장 하 는 과정 으로 실질 적 인 연산 이 없다.현재 우 리 는 이 되 돌아 오 는 구 조 를 옮 겨 다 니 며 구조 중의 function 0 을 하나씩 실행 하 는 방법 이 필요 합 니 다.
 

1 sealed trait Trampoline[+A] { 2   final def runT: A =
3     this match { 4       case Done(a) => a 5       case More(k) => k().runT 6  } 7 } 8 
9 even(1 |-> 123001).runT                           //> res0: Boolean = false

 
이 runT 는 끝 재 귀 (Tail Call Elimination TCE) 알고리즘 이기 때문에 StackOverflow Error 가 나타 나 지 않 았 습 니 다.
실제로 scalaz 도 Trampoline 유형: scalaz / Free. scala 를 제공 합 니 다.

  /** A computation that can be stepped through, suspended, and paused */ type Trampoline[A] = Free[Function0, A] ... object Trampoline extends TrampolineInstances { def done[A](a: A): Trampoline[A] = Free.Return[Function0,A](a) def delay[A](a: => A): Trampoline[A] = suspend(done(a)) def suspend[A](a: => Trampoline[A]): Trampoline[A] = Free.Suspend[Function0, A](() => a) }

Trampoline 은 바로 Free [S, A] 의 특례 이다.S = = Function 0, 또는 Trampoline 은 Free 가 Function 0 을 대상 으로 생 성 된 Monad 입 니 다. 우 리 는 free. Return 과 Free. Suspend 로 Done 과 More 를 실현 할 수 있 기 때 문 입 니 다.우 리 는 scalaz 의 Trampoline 을 even, odd 함수 에 사용 할 수 있 습 니 다.

 1 import scalaz.Free.Trampoline  2 def even(xa: List[Int]): Trampoline[Boolean] =
 3  xa match {  4     case Nil => Trampoline.done(true)  5     case h :: t => Trampoline.suspend(odd(t))  6   }                                               //> even: (xa: List[Int])scalaz.Free.Trampoline[Boolean]
 7 def odd(xa:  List[Int]): Trampoline[Boolean] =
 8  xa match {  9     case Nil => Trampoline.done(false) 10     case h :: t => Trampoline.suspend(even(t)) 11   }                                               //> odd: (xa: List[Int])scalaz.Free.Trampoline[Boolean]
12   
13 even(1 |-> 123001).run                            //> res0: Boolean = false

문법 은 우리 가 정의 한 Trampoline 과 차이 가 많 지 않다.그러면 우 리 는 Trampoline 을 위의 어떤 zipIndex 함수 에 사용 하여 StackOverflow Error 문 제 를 해결 할 수 있 습 니까?zipIndex 에서 문 제 를 일 으 킨 Monad 는 State Monad 입 니 다. 우 리 는 State. lift 로 State [S, A 를 State T [Trampoline, S, A] 로 승격 할 수 있 습 니 다. 먼저 이 lift 함수: scalaz / State T. scala 를 보십시오. 
 

 def lift[M[_]: Applicative]: IndexedStateT[({type λ[α]=M[F[α]]})#λ, S1, S2, A] = new IndexedStateT[({type λ[α]=M[F[α]]})#λ, S1, S2, A] { def apply(initial: S1): M[F[(S2, A)]] = Applicative[M].point(self(initial)) }

이 함수 의 기능 은 State. lift [Trampoline] > > State T [Tarmpoline, S, A] 와 같 습 니 다. 다른 간단 한 예 를 먼저 보 세 요.

1 def incr: State[Int, Int] =  State {s => (s+1, s)}//> incr: => scalaz.State[Int,Int]
2 incr.replicateM(10000).eval(0) take 10            //> java.lang.StackOverflowError
3 
4 import scalaz.Free.Trampoline 5 incr.lift[Trampoline].replicateM(100000).eval(0).run.take(10) 6                                                   //> res0: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

위의 예 에서 도 State Monad 를 사 용 했 습 니 다. 함수 incr 는 State 로 되 돌 아 왔 습 니 다. 이때 replicateM (10000). eval (0) 으로 10000 개 State 를 반복 적 으로 연산 할 때 StackOverflow Error 가 발생 했 습 니 다. 우 리 는 lift 를 따라 incr 를 State T [Trampoline, S, A] 로 되 돌 렸 습 니 다. 이때 replicateM (10000). eval (0) 의 역할 은 구조 전환 (State. apply: Trampoline [(S, A)]) 하 는 것 입 니 다., 다시 Trampoline. run 을 Interpreter 스 트 리밍 구조 로 연산 합 니 다. lift 로 Trampoline 을 승격 한 후 StackOverflow Error 를 해결 하 였 습 니 다.
zipIndex 함 수 를 조정 해 보 겠 습 니 다.

 1 def safeZipIndex[A](xa: List[A]): List[(Int,A)] =
 2  (xa.foldLeft(State.state[Int,List[(Int,A)]](List()))(  3     (acc,a) => for {  4       xn <- acc  5       s <- get[Int]  6       _ <- put(s + 1)  7     } yield (s,a) :: xn  8   ).lift[Trampoline]).eval(1).run.reverse         //> safeZipIndex: [A](xa: List[A])List[(Int, A)]
 9   
10   safeZipIndex(1 |-> 1000).take(10)               //> res2: List[(Int, Int)] = List((1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (7,7), (8,8), (9,9), (10,10))

겉 으로 는 결과 가 맞 는 것 같 습 니 다. 좀 큰 List 를 시도 해 보 세 요.

1  safeZipIndex(1 |-> 10000).take(10)   //> java.lang.StackOverflowError 2                                       //| at scalaz.IndexedStateT$$anonfun$flatMap$1.apply(StateT.scala:62) 3                                       //| at scalaz.IndexedStateT$$anon$10.apply(StateT.scala:95) 4                                       //| at scalaz.IndexedStateT$$anonfun$flatMap$1.apply(StateT.scala:62)
5 ... 6  

아니면 StackOverflow Error 입 니까? 잘못된 힌트 는 State. flatMap 에 의 한 것 입 니 다. 늦 은 점 은 incr 의 원리 에 따라 foldLeft 연산 단계 의 결 과 를 나 누 어 분석 해 야 할 것 같 습 니 다.
이상 에서 우 리 는 Trampoline 이 연속 연산 을 데이터 구 조 를 만 들 고 힙 메모리 로 stack 을 바 꾸 어 재 귀 알고리즘 운행 의 안전 을 보장 할 수 있다 는 것 을 증명 했다. Trampoline 은 Free 의 특례 이기 때문에 Free Interpreter 도 재 귀 알고리즘 의 안전 한 운행 을 보장 할 수 있다. 지금 은 이러한 결론 을 얻 을 수 있다. FP 는 Monadic Programming 이 고 Monad 로 프로 그래 밍 하 는 것 이다.우 리 는 가능 한 한 Free 로 Monad 를 생 성하 고 Free 로 프로 그래 밍 을 해서 FP 프로그램의 신뢰성 을 확보 해 야 한다.