Scalaz (28) - ST Monad: FP 방식 적용 변수

함수 식 프로 그래 밍 모델 은 순수 코드 (pure code) 를 강조 하 는데 주요 실현 방식 은 가 변 적 이지 않 은 데이터 구 조 를 사용 하 는 것 이 고 함수 조합 (composability) 이 최종 적 으로 함수 구성 요소 의 중복 사용 을 실현 하 는 것 이 목적 이다.그러나 만약 에 우리 가 한 함수 p 내부 에서 가 변 수 를 사용 했다 면 (mutable variables) 함수 의 입력 매개 변수 e 가 순 코드 라면 표현 식 p (e) 역시 순 코드 입 니 다. 함수 호출 자 는 함수 내부 에 명 시 된 이 가 변 수 를 접 할 수 없 기 때 문 입 니 다.그러나 이러한 방법 은 함수 의 비대 한 코드 를 만 들 수 있 습 니 다. 함수 내부 에 서 는 함수 조합 을 실현 할 수 없 기 때문에 함수 구성 요 소 를 중복 사용 할 수 없고 실제 적 으로 FP 의 취지 에 어 긋 납 니 다.Scalaz 는 병렬 연산 환경 에서 각 스 레 드 가 상호 간 의 변수, 즉 ST Monad 에 영향 을 주지 않 더 라 도 변수 사용 문 제 를 해결 하 는 방법 을 제공 합 니 다.
Scalaz 의 변 수 는 두 가지 로 나 눌 수 있 습 니 다. 메모리 주소 STRF 나 가 변 배열 STArray 입 니 다.소스 코드 에서 의 정의: effect / ST. scala

/**Mutable variable in state thread S containing a value of type A. [[http://research.microsoft.com/en-us/um/people/simonpj/papers/lazy-functional-state-threads.ps.Z]] */
sealed trait STRef[S, A] { protected var value: A /**Reads the value pointed at by this reference. */ def read: ST[S, A] = returnST(value) /**Modifies the value at this reference with the given function. */ def mod[B](f: A => A): ST[S, STRef[S, A]] = st((s: Tower[S]) => { value = f(value); (s, this) }) /**Associates this reference with the given value. */ def write(a: => A): ST[S, STRef[S, A]] = st((s: Tower[S]) => { value = a; (s, this) }) /**Synonym for write*/ def |=(a: => A): ST[S, STRef[S, A]] = write(a) /**Swap the value at this reference with the value at another. */ def swap(that: STRef[S, A]): ST[S, Unit] = for { v1 <- this.read v2 <- that.read _ <- this write v2 _ <- that write v1 } yield () } ... /**Mutable array in state thread S containing values of type A. */
sealed trait STArray[S, A] { def size: Int def z: A implicit def manifest: Manifest[A] private lazy val value: Array[A] = Array.fill(size)(z) import ST._ /**Reads the value at the given index. */ def read(i: Int): ST[S, A] = returnST(value(i)) /**Writes the given value to the array, at the given offset. */ def write(i: Int, a: A): ST[S, STArray[S, A]] = st(s => { value(i) = a; (s, this) }) /**Turns a mutable array into an immutable one which is safe to return. */ def freeze: ST[S, ImmutableArray[A]] = st(s => (s, ImmutableArray.fromArray(value))) /**Fill this array from the given association list. */ def fill[B](f: (A, B) => A, xs: Traversable[(Int, B)]): ST[S, Unit] = xs match { case Nil             => returnST(()) case ((i, v) :: ivs) => for { _ <- update(f, i, v) _ <- fill(f, ivs) } yield () } /**Combine the given value with the value at the given index, using the given function. */ def update[B](f: (A, B) => A, i: Int, v: B) = for { x <- read(i) _ <- write(i, f(x, v)) } yield () }

우 리 는 STRF 와 STArray 가 write, mod, update 와 같은 부작용 이 있 는 조작 함 수 를 정의 하 는 것 을 보 았 다. 그들 은 모두 ST [S, STRF [S, A] 형식의 결 과 를 되 돌려 주 었 다.ST 는 Monad 입 니 다. 원본 코드 에서 확인 할 수 있 습 니 다. 

/** * Purely functional mutable state threads. * Based on JL and SPJ's paper "Lazy Functional State Threads" */
sealed trait ST[S, A] { private[effect] def apply(s: Tower[S]): (Tower[S], A) import ST._ def flatMap[B](g: A => ST[S, B]): ST[S, B] = st(s => apply(s) match { case (ns, a) => g(a)(ns) }) def map[B](g: A => B): ST[S, B] = st(s => apply(s) match { case (ns, a) => (ns, g(a)) }) }

ST 는 State Monad 와 매우 비슷 하고 맵 과 flatMap 이 준비 되 어 있 기 때문에 Monad 로 for - comprehension 을 지원 할 수 있 습 니 다.우 리 는 ST 의 for - comprehension 을 통 해 STRef, STArray 조작 함수 의 조합 을 실현 할 수 있 습 니 다. 이 조작 함수 들 의 반환 결 과 는 모두 ST 형식 이기 때 문 입 니 다.그러나 write, mod 이러한 조작 함수 들 은 공통 적 으로 이상 한 현상 이 있 습 니 다. 그들 은 모두 S 형식의 값 을 호출 한 적 이 없고 들 어 오 는 대로 출력 합 니 다.이것 은 바로 ST Monad 가 어떻게 명명 한 것 입 니까? ST 는 State Tag 라 고도 할 수 있 습 니 다. 즉, 모든 작업 에 독립 된 상태 유형 S 가 있 습 니 다. S 유형 이 다 르 면 조작 함 수 를 호출 할 수 없습니다.한편, for - comprehension 은 직렬 프로 세 스 로 스 레 드 간 에 교차 운행 하지 않 고 각자 의 변수 에 영향 을 줄 수 있 습 니 다.ST Monad 와 State Monad 의 가장 큰 차이 점 은 run 방법 이 없다 는 것 이다. 즉, 우 리 는 ST 의 내부 방법 으로 ST [S, A] 의 A 값 을 얻 을 수 없다 는 것 이다.먼저 STRef 와 STArray 의 사례 를 살 펴 보 겠 습 니 다.
 

 1 import scalaz._  2 import Scalaz._  3 import effect._  4 import ST._  5 object st {  6 def e1[S] = for {  7   r <- newVar[S](3)  8   x <- r.mod {_ + 2}  9 } yield x                                         //> e1: [S]=> scalaz.effect.ST[S,scalaz.effect.STRef[S,Int]]
10 
11 def e2[S] = for { 12   r <- newVar[S](3) 13   x <- r.mod {_ + 2} 14   y <- x.read 15 } yield y                                         //> e2: [S]=> scalaz.effect.ST[S,Int]
16 
17 def e3[S] = for { 18   arr <- newArr[S,Int](5,0) 19   _ <- arr.write(0,3) 20   _ <- arr.write(1,2) 21   _ <- arr.update ((a: Int,b: Int) => a + b, 2, 4) 22   r <- arr.freeze 23 } yield r                                         //> e3: [S]=> scalaz.effect.ST[S,scalaz.ImmutableArray[Int]]

 
new Var [S] (3) 상태 S 로 Int 주 소 를 새로 만 들 고 값 3 을 저장 합 니 다.mod 작업 은 ST [S, STRF [S, Int] 를 되 돌려 주 고 주소 (reference) 를 되 돌려 주 며 read 는 ST [S, Int] 를 되 돌려 주 며 값 입 니 다.우선 e1 [S], e2 [S], e3 [S] 에 독립 상태 라벨 S 가 붙 어 있 습 니 다.
지금 우 리 는 ST Monad 에서 연산 결 과 를 꺼 내야 한다.위의 분석 을 통 해 우 리 는 두 가지 방식 에 직면 할 수 있다. 그것 이 바로 ST [S, A], ST [S, STRF [S, A] 이다.ST [S, A] 에서 꺼 낸 것 은 A 형식의 값 이 고, ST [S, STRF [S, A] 에서 꺼 낸 것 은 메모리 주소 입 니 다.만약 우리 가 어떤 방식 을 통 해 메모리 주 소 를 얻 을 수 있다 면 함수 체 외 에서 주소 내의 값 을 수정 할 수 있 고 부작용 이 발생 할 수 있 음 을 예견 할 수 있다.Scalaz 의 해결 방법 은 고급 클래스 매개 변수 다 중 (2nd - rank parameteric polymorphism) 을 통 해 컴 파일 러 (copiler) 를 이용 하여 ST [S, STRF [S, A] 와 같은 읽 기 동작 을 컴 파일 하지 않 는 것 입 니 다.다음은 시범 결 과 를 살 펴 보 자.

1 runST(new Forall[({type l[x] = ST[x, Int]})#l]{def apply[S] = e2[S]}) 2                                                   //> res0: Int = 5 3 //runST(new Forall[({type l[x] = ST[x, Int]})#l]{def apply[S] = e1[S]}) 4 //type mismatch; found : scalaz.effect.ST[S,scalaz.effect.STRef[S,Int]] required: scalaz.effect.ST[S,Int] 

e1 은 ST [S, STRef [S, A]], 표현 식 new Forall [({type l [x] = ST [x, Int]}) \ # l] {def apply [S] = e1 [S]} 을 컴 파일 할 수 없습니다.여기 서 Forall 은 고급 클래스 매개 변수 다 중 클래스 입 니 다. 정 의 는 다음 과 같 습 니 다.

/** A universally quantified value */ trait Forall[P[_]] { def apply[A]: P[A] }

우 리 는 위 에 있 는 코드 를 다시 조직 하여 모두 가 좀 더 분명하게 볼 수 있 도록 한다.
 

1 type ForallST[A] = Forall[({type l[x] = ST[x,A]})#l] 2 runST(new ForallST[Int]{ def apply[S] = e2[S] })  //> res0: Int = 5 3 //runST(new ForallST[Int]{def apply[S] = e1[S]}) 4 //type mismatch; found : scalaz.effect.ST[S,scalaz.effect.STRef[S,Int]] required: scalaz.effect.ST[S,Int]

 
오류 정 보 를 통 해 알 수 있 듯 이 컴 파일 러 가 기대 하 는 유형 은 ST [S, Int] 이 고 ST [S, STRF [S, Int] 는 유형 오류 가 발생 한 것 이다.고급 클래스 매개 변수 다 중 클래스 f 를 이용 하여 new Forall {def apply [A] > > ST [S, A]} 과 같은 디자인 만 컴 파일 할 수 있 습 니 다.
State Monad 와 비교 하면 ST Monad 는 연산 값 을 가 져 오기 위 한 run 함 수 를 포함 하지 않 습 니 다.ST Monad 는 형식 외 에 연산 값 을 읽 는 함수 runST 를 정의 합 니 다.
runST 방법의 정 의 는 다음 과 같 습 니 다.

  /**Run a state thread */ def runST[A](f: Forall[({type λ[S] = ST[S, A]})#λ]): A = f.apply.apply(ivoryTower)._2

State Monad 에서 연산 값 을 가 져 오 는 방식 은 다음 과 같 습 니 다. someState. run (svalue), svalue 는 S 형식 값 으로 상태 초기 값 입 니 다.우 리 는 모든 변수 조작 함수 가 S 형식 값 을 사용 하지 않 았 다 는 것 을 알 고 있 기 때문에 위의 f. apply. apply (ivory Tower) 에서 이 ivory Tower 는 의미 없 는 임의의 형식 값 입 니 다. 우 리 는 어떠한 S 값 도 주입 하여 연산 결과 값 을 가 져 올 필요 가 없습니다.