Stackless Scala With Free Monads
Rúnar Óli Bjarnason <-- to type 'ú' : Option e + u
2014
문제: State 모나드가 있다.
def zipIndex[A](as: List[A]): List[(Int, A)] = ...
List[A]를 Index와 pair로 만들어주는 zipIndex를 구현하는데...
여기 굳이 State 모나드를 사용할 필요는 없다.
하지만 여기선.. 문제 상황을 만들기 위해 굳이 State 모나드를 사용할 수 있다.
case class State[S,+A](runS: S => (A, S)) {
def map
def flatMap
}
def get[S]: State[S,S] = State(s => (s,s))
def put[S](s:S): State[S,Unit] = State(_ => ((),s))
def pure[S, A](a:A): State[S,A] = State(s => (a,s))
index를 상태로 본다면, 0에서 시작, 1씩 증가시키면서 설정하면 된다. State[Int, List[Int,A]]인 셈.
def zipIndex[A](as: List[A]): List[(Int, A)] =
as.foldLeft(pure[Int, List[(Int,A)]](List()))((acc,a) => for {
xs <- acc
i <- get
_ <- put(i+1)
} yield (i, a) :: xs).runS(0)._1.reverse
foldLeft는 tailrec이지만, 여기서는 그 결과가 State[Int, List[(Int,A)]]의 연산 과정. runS(0)에서 비로소 전체 List를 순회하면서 0,1,2,...상태가 바뀌고 List를 만들어낸다. 이 과정은 State.flatMap의 체인으로 진행.
그런데.. flatMap 구현을 보면..
case class State[S,+A](runS: S => (A, S)) {
def flatMap[B](f: A => State[S,B]): State[S,B] =
State[S,B](s => { val (a,s') = runS(s); f(a).runS(s') })
}
runS를 부르면 flatMap을 부르고, flatMap은 runS를 부르고, 다시 flatMap을 부르고... 그래서 List가 크면 금방 StackOverflowError가 뜬다.
이 문제는.. 사실 Scala에서 좀더 엄격하게 함수형 프로그래밍을 하고자 할 때 발생한다. 함수형 프로그래밍을 널리 전파하려는 Rúnar 입장에서는 이 문제를 해결해줘야 사람들 불만이 없을 거다.
해결책:
1. TailRec보다 좀더 일반화된 Trampoline(monad)
2. Trampoline에서 StackOverflowError를 회피하고 -- flatMap을 타입으로 표현한 것이 주요 방법
3. 이를 일반화시켜 Free Monad를 완성
그래서 Haskell Free Monad와 다른 모양이 나오게 되었다.
data Free f a = Pure a | Free f (Free f a)
sealed trait Free[S[+_], +A] {
private case class FlatMap[S[+_],A,+B](a: Free[S,A], f: A => Free[S,B]) extends Free[S,B]
}
case class Done[S[+_],+A](a: A) extends Free[S,A]
case class More[S[+_],+A](k: S[Free[S,A]]) extends Free[S,A]
Done/More는 각각 Pure/Free에 매핑되는데, FlatMap은 스택 문제로 추가된 것이다.
Rúnar Óli Bjarnason <-- to type 'ú' : Option e + u
2014
문제: State 모나드가 있다.
def zipIndex[A](as: List[A]): List[(Int, A)] = ...
List[A]를 Index와 pair로 만들어주는 zipIndex를 구현하는데...
여기 굳이 State 모나드를 사용할 필요는 없다.
하지만 여기선.. 문제 상황을 만들기 위해 굳이 State 모나드를 사용할 수 있다.
case class State[S,+A](runS: S => (A, S)) {
def map
def flatMap
}
def get[S]: State[S,S] = State(s => (s,s))
def put[S](s:S): State[S,Unit] = State(_ => ((),s))
def pure[S, A](a:A): State[S,A] = State(s => (a,s))
index를 상태로 본다면, 0에서 시작, 1씩 증가시키면서 설정하면 된다. State[Int, List[Int,A]]인 셈.
def zipIndex[A](as: List[A]): List[(Int, A)] =
as.foldLeft(pure[Int, List[(Int,A)]](List()))((acc,a) => for {
xs <- acc
i <- get
_ <- put(i+1)
} yield (i, a) :: xs).runS(0)._1.reverse
foldLeft는 tailrec이지만, 여기서는 그 결과가 State[Int, List[(Int,A)]]의 연산 과정. runS(0)에서 비로소 전체 List를 순회하면서 0,1,2,...상태가 바뀌고 List를 만들어낸다. 이 과정은 State.flatMap의 체인으로 진행.
그런데.. flatMap 구현을 보면..
case class State[S,+A](runS: S => (A, S)) {
def flatMap[B](f: A => State[S,B]): State[S,B] =
State[S,B](s => { val (a,s') = runS(s); f(a).runS(s') })
}
runS를 부르면 flatMap을 부르고, flatMap은 runS를 부르고, 다시 flatMap을 부르고... 그래서 List가 크면 금방 StackOverflowError가 뜬다.
이 문제는.. 사실 Scala에서 좀더 엄격하게 함수형 프로그래밍을 하고자 할 때 발생한다. 함수형 프로그래밍을 널리 전파하려는 Rúnar 입장에서는 이 문제를 해결해줘야 사람들 불만이 없을 거다.
해결책:
1. TailRec보다 좀더 일반화된 Trampoline(monad)
2. Trampoline에서 StackOverflowError를 회피하고 -- flatMap을 타입으로 표현한 것이 주요 방법
3. 이를 일반화시켜 Free Monad를 완성
그래서 Haskell Free Monad와 다른 모양이 나오게 되었다.
data Free f a = Pure a | Free f (Free f a)
sealed trait Free[S[+_], +A] {
private case class FlatMap[S[+_],A,+B](a: Free[S,A], f: A => Free[S,B]) extends Free[S,B]
}
case class Done[S[+_],+A](a: A) extends Free[S,A]
case class More[S[+_],+A](k: S[Free[S,A]]) extends Free[S,A]
Done/More는 각각 Pure/Free에 매핑되는데, FlatMap은 스택 문제로 추가된 것이다.
